perm filename V2E.IN[TEX,DEK] blob
sn#359280 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00011 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 196 galley 1
C00016 00003 folio 198 galley 2
C00030 00004 folio 201 galley 3
C00044 00005 folio 204 galley 4
C00061 00006 folio 206 galley 5
C00078 00007 folio 209 galley 6
C00094 00008 folio 212 galley 7
C00103 00009 folio 214 galley 8
C00118 00010 folio 216 galley 9
C00136 00011 folio 220 galley 10
C00149 ENDMK
C⊗;
folio 196 galley 1
0 {U0}{H10L12M29}|πW58320#Computer Programming!(Knuth/Addison-
1 Wesley)!f.|4196!ch.|43!g.|41d|'{A6}!|9|7First
3 it is convenient to generalize De_nition A, since
11 the limit appearing there does not exist for
19 all sequences. Let us de_ne|'{A4}|v4Pr|){H12}({H10}|εS(n){H1
24 2}){H10}|4α=↓|4|uw|πlim|4sup|uc|)|.|εn|1|¬M|1|¬X|)|4{H12}({H
24 10}|≤n(n)/n{H12}){H10}!!|πPr{H12}({H10}|εS(n){H12}){H10}|4α=
24 ↓|4|uw|πlim|4inf|uc|)|.|εn|1|¬M|1|¬X|)|4{H12}({H10}|≤n(n)/n{
24 H12}){H10}.|J!(7)};{A9}|πThen Pr{H12}(|εS(n){H12}){H10},
27 |πif it exists, is the common value of Pr{H12}({H10}|εS(n){H
35 12}) |πand |v4Pr|){H12}({H10}|εS(n){H12}){H10}.|'
38 !|9|7|πWe have seen that a |εk-|πdistributed
44 [0,|41) sequence leads to a |εk-|πdistributed
50 |εb|π-ary sequence, if |εU |πis replaced by |"l|εbU|"L.
58 |πOur _rst theorem shows that a converse result
66 is true:|'{A12}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡A|≡.|9|4|εLet
70 |↔b|"lb|βjU|βn|↔L|↔v|4α=↓|4U|β0,|4U|β1,|4U|β2,|4.|4.|4.|4be
71 a [0,|41) sequence. If the sequence|'{A9}|↔b|"lb|βjU|βn|"L|↔
77 v|4α=↓|4|↔lb|βjU|β0|"L, |"lb|βjU|β1|"L, |"lb|βjU|β2|"L,|4.|4
79 .|4.|;{A9}is a k-distributed b|βj-ary sequence
85 for all b|βj in an in⊂nite sequence of integers,
94 1|4|¬W|4b|β1|4|¬W|4b|β2|4|¬W|4b|β3|4|¬W|4αo↓|4αo↓|4αo↓|4,
95 then the original sequence |↔bU|βn|↔v is k-distributed.|'
102 {A12}!|9|7|πAs an example of this theorem, suppose
109 that |εb|βj|4α=↓|42|gj. |πThe sequence |"l|ε2|gjU|β0|"L,
114 |"l2|gjU|β1|"L,|4.|4.|4. |πis essentially the
118 sequence of the _rst |εj |πbits of the binary
127 representation of |εU|β0,|4U|β1,|4.|4.|4.|4.
130 |πIf all these integer sequences are |εk-|πdistributed,
137 in the sense of De_nition |εD, |πthe real-valued
145 sequence |εU|β0,|4U|β1,|4.|4.|4. |πmust also
149 be |εk-|πdistributed in the sense of De_nition
156 B.|'{A12}|εProof of Theorem A.|9|4|πIf the sequence
163 |ε|"lbU|β0|"L, |"lbU|β1|"L,|4.|4.|4. |πis |εk-|πdistributed,
166 it follows by the addition of probabilities
174 that Eq. (5) holds whenever each |εu|βj |πand
182 |εv|βj |πis a rational number with denominator
189 |εb. |πNow let |εu|βj,|4v|βj |πbe any real numbers,
197 and let |εu|ur|↔0|)j|)|4|¬E|4U|βJ|4|¬W|4U|ur|↔0|)j|)|4α+↓|41
199 /b, v|ur|↔0|)j|)|4|¬E|4v|βj|4|¬W|4v|ur|↔0|)j|)|4α+↓|41/b.|;
201 {A9}|πLet |εS(n) |πbe the statement that |εu|β1|4|¬E|4U|βn|4
207 |¬W|4v|β1,|4.|4.|4.|4,|4u|βk|4|¬E|4U|βn|βα+↓|βk|βα_↓|β1|4|¬W
207 |4v|βk. |πWe have|'{A9}Pr{H12}(|εS(n){H12}){H10}|4|¬E|4|πPr|
210 ↔a|εu|ur|↔0|)1|)|4|¬E|4U|βn|4|¬W|4v|ur|↔0|)1|)|4α+↓|4|(1|d2b
210 |)|4,|4.|4.|4.|4,|4u|ur|↔0|)k|)|4|¬E|4U|βn|βα+↓|βk|βα_↓|β1|4
210 |¬W|4v|ur|↔0|)k|)|4α+↓|4|(1|d2b|)|↔s|'{A4}α=↓|4|↔av|ur|↔0|)1
211 |)|4α_↓|4u|ur|↔0|)1|)|4α+↓|4|(1|d2b|)|↔s|4.|4.|4.|4|↔av|ur|↔
211 0|)k|)|4α_↓|4u|ur|↔0|)k|)|4α+↓|4|(1|d2b|)|↔s;|?
212 {A6}|πPr{H12}({H10}|εS(n){H12}){H10}|4|¬R|4|πPr|↔a|εu|ur|↔0|
212 )1|)|4α+↓|4|(1|d2b|)|4|¬E|4U|βn|4|¬W|4v|ur|↔0|)1|),|4.|4.|4.
212 |4,|4U|ur|↔0|)k|)|4α+↓|4|(1|d2b|)|4|¬E|4U|βn|βα+↓|βk|βα_↓|β1
212 |4|¬W|4v|ur|↔0|)k|)|↔s|'{A4}α=↓|4|↔av|ur|↔0|)1|)|4α_↓|4u|ur|
213 ↔0|)1|)|4α_↓|4|(1|d2b|)|↔s|4.|4.|4.|4|↔av|ur|↔0|)k|)|4α_↓|4u
213 |ur|↔0|)k|)|4α_↓|4|(1|d2b|)|↔s.|1|?{A9}|πNow
215 |¬G(|εv|ur|↔0|)j|)|4α_↓|4u|ur|↔0|)j|)|4|¬N|41/b)|4α_↓|4(v|βj
215 |4α_↓|4u|βj)|¬G|4|¬E|42/b; |πsince our inequalities
219 hold for all |εb|4α=↓|4b|βj, |πand since |εb|βj|4|¬M|4|¬X
226 |πas |εj|4|¬M|4|¬X, |πwe have|'{A9}(|εv|β1|4α_↓|4u|β1)|4.|4.
230 |4.|4(v|βk|4α_↓|4u|βk)|4|¬E|4|πPr{H12}({H10}|εS(n){H12}){H10
230 }|4|¬E|4|πPr{H12}({H10}|εS(n){H12})|4|¬E|4(v|β1|4α_↓|4u|β1)|
230 4.|4.|4.|4(v|βk|4α_↓|4u|βk).|'{A9}!|9|7|πThe
232 next theorem is our main tool for proving things
241 about |εk-|πdistributed sequences.|'{A12}|≡T|≡h|≡e|≡o|≡r|≡e|
244 ≡m |≡B|≡.|9|4|εLet |↔bU|βn|↔v be a k-distributed
250 [0,|41) sequence, and let f(x|β1,|4x|β2,|4.|4.|4.|4,|4x|βk)
255 be a Riemann-integrable function of k variables|*/;|\
262 then|'{A9}|uw|πlim|uc|)|ε|.n|¬M|¬X|)|4|(1|d2n|)|4|¬K|uc|)0|¬
263 Ej|¬Wn|)|4f(U|βj,|4U|βj|βα+↓|β1,|4.|4.|4.|4,|4U|βj|βα+↓|βk|β
263 α_↓|β1)|'{A4}α=↓|4|↔j|ur1|)0|)|4.|4.|4.|4|↔j|ur1|)0|)|4f(x|β
264 1,|4x|β2,|4.|4.|4.|4,|4x|βk)|4dx|β1|4.|4.|4.|4dx|βk.!(8)|?
265 {A9}Proof.|9|4|πThe de_nition of a |εk-|πdistributed
270 sequence states that this result is true in the
279 special case that|'{A9}|εf(x|β1,|4.|4.|4.|4,|4x|βk)|4α=↓|4|↔
282 A|(1,!!|d50,!!|)|(|πif!!|εu|β1|4|¬E|4x|β1|4|¬W|4v|β1,|4.|4.|
282 4.|4,|4u|βk|4|¬E|4x|βk|4|¬W|4v|βk;|d5!|)|J!(9)|;
283 {A9}|πTherefore Eq. (8) is true whenever |εf|4α=↓|4a|β1f|β1|
289 4α+↓|4a|β2f|β2|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4a|βmf|βm
290 |πand when each |εf|βj |πis a function of type
299 (9); in otherwords, Eq. (8) holds whenever |εf
307 |πis a ``step-function;; obtained by (i) partitioning
314 the unit |εk-|πdimensional cube into subcells
320 whose faces are parallel to the coordinate axes,
328 and (ii) assigning a constant value to |εf |πon
337 each subcell.|'!|9|7Now let |εf |πbe any Riemann-integrable
345 function. If |ε|≤e |πis any positive number,
352 we know (by the de_nition of Riemann-integrability)
359 that there exist step functions |εf |πand |ε|=|¬∩f
367 |πsuch that |εf(x|β1,|4.|4.|4.|4,|4x|βk)|4|¬E|4f(x|β1,|4.|4.
369 |4.|4,|4x|βk)|4|¬E|4|=|¬∩f(x|β1,|4.|4.|4.|4,|4x|βk),
370 |πand such that the di=erence of the integrals
378 of |εf |πand |ε|=|¬∩f |πis less than |ε|≤e. |πSince
387 Eq. (8) holds for |εf |πand |ε|=|¬∩f, |πand since|'
396 {A9}|(|ε1|d2n|)|4|↔k|uc|)0|¬Ej|¬Wn|)|4f(U|βj,|4.|4.|4.|4,|4U
396 |βj|βα+↓|βk|βα_↓|β1)|4|¬E|4|(1|d2n|)|4|↔k|uc|)0|¬Ej|¬Wn|)|4f
396 (U|βj,|4.|4.|4.|4,|4U|βj|βα+↓|βk|βα_↓|β1)|5|;
397 {A4}|hn|4|β0|β|¬E|βj|β|¬W|βn|4f(U|βj,|4.|4.|4.|4,|4U|βj|βα+↓
397 |βk|βα_↓|β1)|4|n|¬E|4|(1|d2n|)|4|↔k|uc|)0|¬Ej|¬Wn|)|4|=|¬∩f(
397 U|βj,|4.|4.|4.|4,|4U|βj|βα+↓|βk|βα_↓|β1),|;{A9}|πwe
399 conclude Eq. (8) is true also for |εf.|'{A12}!|9|7|πAs
408 the _rst application of this theorem, consider
415 the |εpermutation test |πdescribed in Section
421 3.3.2. Let (|εp|β1,|4p|β2,|4.|4.|4.|4,|4p|βk)
424 |πbe any permutation of the numbers 1,|42,|4.|4.|4.|4,|4|εk;
430 |πwe want to show that|'{A9}Pr(|εU|βn|βα+↓|βp|m1|βα_↓|β1|4|
436 ¬W|4U|βn|βα+↓|βp|m2|βα_↓|β1)|4α=↓|41/k*3.|J!(10)|;
437 {A9}|πTo prove this, assume that the sequence
444 |↔b|εU|βn|↔v |πis |εk-|πdistributed, and let|'
449 {A9}|εf(x|β1,|4.|4.|4.|4,|4x|βk)|4α=↓|4|(1,!!|d50,!!|)|(|πif
449 !!|εx|βp|m1|4|¬E|4x|βp|m2|4|¬E|4αo↓|4αo↓|4αo↓|4|¬E|4x|βp|mk|
449 d5!|)|;{A9}|πWe have|'{A3}Pr(|εU|βn|βα+↓|βp|m1|βα_↓|β1|4|¬W|
452 4U|βn|βα+↓|βp|m2|βα_↓|β1|4|¬W|4αo↓|4αo↓|4αo↓|4|¬W|4U|βn|βα+↓
452 |βp|mk|βα_↓|β1)|'{A4}|∂α=↓|4|↔j|ur1|)0|)|4.|4.|4.|4|↔j|ur1|)
453 0|)|4f(x|β1,|4.|4.|4.|4,|4x|βk)|4dx|β1|4.|4.|4.|4dx|βk|h|m1|
453 4α=↓|4k*3|4.|n|?{A4}|Lα=↓|4|↔j|ur1|)0|)|4dx|βp|mk|4|↔j|urx|βp
454 |mk|)0|)|4.|4.|4.|4|↔j|urx|βp|m3|)0|)|4dx|βp|m2|4|↔j|urx|βp|
454 m2|)0|)|4dx|βp|m1|4α=↓|4|(1|d2k*3|)|4.>{A9}|π|≡C|≡o|≡r|≡o|≡l|
455 ≡l|≡a|≡r|≡y |≡P|≡.|9|4|εIf a [0,|41) sequence
460 is k-distributed, it satis⊂es the permutation
466 test of order k, in the sense of Eq. (10).|'{A12}!|9|7|πWe
477 can also show that the |εserial correlation test
485 |πis satis_ed:|'{A12}|≡C|≡o|≡r|≡o|≡l|≡l|≡a|≡r|≡y
488 |≡S|≡.|9|4|εIf a [0,|41) sequence is (k|4α+↓|41)-distributed
493 , the serial correlation coe∀cient between U|βn
500 and U|βn|βα+↓|βk tends to zero|*/:|'|\{A9}|uw|πlim|uc|)|.|εn|
505 ¬M|¬X|)|4|(|(1|d2n|)|4|¬K|4U|βjU|βj|βα+↓|βk|4α_↓|4|↔a|(1|d2n
505 |)|4|¬K|4U|βj|↔s|↔a|(1|d2n|)|4|¬K|4U|βj|βα+↓|βk|↔s|d1|↔K|v2|
505 ↔a|(1|d2n|)|4|¬K|4U|ur2|)j|)|4α_↓|4|↔a|(1|d2n|)|4|¬K|4U|βj|↔
505 s|g2|↔s|↔a|(1|d2n|)|4|¬K|4U|ur2|)jα+↓k|)|4α_↓|4|↔a|(1|d2n|)|
505 4|¬K|4U|βj|βα+↓|βk|↔s|g2{H12}|↔s{H10}|)|)|4α=↓|40.|;
506 {A9}(|πAll summations here are for 0|4|¬E|4|εj|4|¬W|4n.)|'
512 {A12}Proof.|9|4|πBy Theorem B, the quantities|'
517 {A9}|(|ε1|d2n|)|4|¬K|4U|βjU|βj|βα+↓|βk,!!|(1|d2n|)|4|¬K|4U|u
517 r2|)j|),!!|(1|d2n|)|4|¬K|4U|ur2|)jα+↓k|),!!|(1|d2n|)|4|¬K|4U
517 |βj,!!|(1|d2n|)|4|¬K|4U|βj|βα+↓|βk|;{A9}|πtend
519 to the respective limits |f1|d34|), |f1|d33|),
525 |f1|d33|), |f1|d32|), |f1|d32|) as |εn|4|¬M|4|¬X.|'
530 |Hu{U0}{H10L12M29}|πW58320#Computer Programming!(Knuth/Addis
folio 198 galley 2
531 on-Wesley)!f.|4198!ch.|43!g.|42d|'{A6}!|9|7Let
533 us now consider some slightly more general distribution
541 properties of sequences. We have de_ned the |εk-|πdistributi
548 on property for all adjacent |εk-|πtuples; for
555 example, a sequence is 2-distributed if and only
563 if the points|'{A6}{A3}(|εU|β0,|4U|β1),!!(U|β1,|4U|β2),!!(U|
566 β2,|4U|β3),!!(U|β3,|4U|β4),!!(U|β4,|4U|β5),!!.|4.|4.|;
567 {A9}|πare equidistributed in the unit square.
573 It is quite possible, however, that the alternate
581 pairs of points, (|εU|β1,|4U|β2), (U|β3,|4U|β4),
586 (U|β5,|4U|β6),|4.|4.|4. |πare not themselves
590 equi|-distributed; if the density of points (|εU|β2|βn|βα_↓|
596 β1, U|β2|βn) |πis de_cient in some area, the
604 other points (|εU|β2|βn, U|β2|βn|βα+↓|β1) |πmight
609 compensate for it. For example, the periodic
616 binary sequence|'{A9}|ε|↔bX|βn|↔v|4α=↓|40, 0,
620 0, 1,!0, 0, 0, 1,!1, 1, 0, 1,!1, 1, 0, 1,!0,
631 0, 0, 1,!.|4.|4.|4,!(11)|?{A9}|πwith a period
637 of length 16, is seen to be 3-distributed; yet
646 the sequence of even-numbered elements |↔b|εX|β2|βn|↔v|4α=↓|
651 40,|40,|40,|40,|41,|40,|41,|40,|4.|4.|4. |πhas
653 three times as many zeros as ones, while the
662 subsequence of odd-numbered elements |↔b|εX|β2|βn|βα+↓|β1|↔v
666 |4α=↓|40,|41,|40,|41,|41,|41,|41,|41,|4.|4.|4.
667 |πhas three times as many ones as zeros.|'!|9|7If
676 a sequence |↔b|εU|βn|↔v |πis |¬X-distributed,
681 the example above shows that it is not at all
691 obvious that the subsequence of alternate terms
698 |↔b|εU|β2|βn|↔v|4α=↓|4U|β0, U|β2, U|β4, U|β6,|4.|4.|4.
702 |πis |¬X-distributed or even 1-distributed. But
708 we shall see that |ε|↔bU|β2|βn|↔v |πis, in fact,
716 |¬X-distributed, and much more is also true.|'
723 {A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|≡n |≡E|≡.|9|4|εA
725 [0,|41) sequence |↔bU|βn|↔v is said to be (m,|4k)-distribute
732 d if|'{A9}|πPr(|εu|β1|4|¬E|4U|βm|βn|βα+↓|βj|4|¬W|4v|β1,
735 u|β2|4|¬E|4U|βm|βn|βα+↓|βj|βα+↓|β1|4|¬W|4v|β2,|4.|4.|4.|4,
736 u|βk|4|¬E|4U|βm|βn|βα+↓|βj|βα+↓|βk|βα_↓|β1|4|¬W|4v|βk)|'
737 {A4}α=↓|4(v|β1|4α_↓|4u|β1)|4.|4.|4.|4(v|βk|4α_↓|4u|βk)|?
738 {A9}for all choices of real numbers u|βr, v|βr
746 with 0|4|¬E|4u|βr|4|¬W|4v|βr|4|¬E|41 for 1|4|¬E|4r|4|¬E|4k,
750 and for all integers j with 0|4|¬E|4j|4|¬W|4m.|'
757 {A12}|πThus a |εk-|πdistributed sequence is the
763 special case |εm|4α=↓|41 |πin De_nition E; the
770 case |εm|4α=↓|42 |πmeans that the |εk-tuples
776 in even positions must have the same density
784 as the |εk-|πtuples in even positions must have
792 the same density as the |εk-|πtuples in odd positions,
801 etc.|'!|9|7Several properties of De_nition E
807 are obvious:|'{A9}!|9|7|εAn (m,|4k)-distributed
811 sequence is (m,|4k)-distributed for 1|4|¬E|4|≤k|4|¬E|4k.|J!(
815 12)|'{A6}!|9|7An (m,|4k)-distributed sequence
819 is (d,|4k)-distributed for all divisors|J!(13)|'
824 !!!|9|5d of m.|'{A9}|πWe can de_ne the concept
832 of an (|εm,|4k)-|πdistributed |εb-|πary sequence,
837 as in De_nition D; and the proof of Theorem A
847 remains valid for (|εm,|4k)-|πdistributed sequences.|'
852 !|9|7The next theorem, which is in many ways
860 rather surprising, shows that the property of
867 being |¬X-distributed is very strong indeed,
873 much stronger than we imagined it to be when
882 we _rst considered the de_nition of the concept.|'
890 {A12}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡C (Ivan Niven and
895 H. S. Zuckerman).|9|4|εAn |¬X-distributed sequence
900 is (m,|4k)-distributed for all positive integers
906 m and k.|'{A12}Proof.|9|4|πIt su∃ces to prove
913 the theorem for |εb-|πary sequences, by using
920 the generalization of Theorem A just mentioned.
927 Furthermore, we may assume that |εm|4α=↓|4k:
933 |πfor, by (12) and (13), the sequence will be
942 (|εm,|4k)-|πdistributed if it is (|εmk,|4mk)-|πdistributed.|
946 '!|9|7So we will prove that |εany |¬X-distributed
954 b-ary sequence X|β0, X|β1,|4.|4.|4. is (m,|4m)-distributed
960 for all positive integers m. |πOur proof is a
969 simpli_cation of the proof given by Niven and
977 Zuckerman in |εPaci⊂c Journal of Mathematics
983 |≡1 (1951), 103<109.|'!|9|7|πThe theorem is proved
990 by making use of an important idea which is useful
1000 in so many mathematical arguments: ``If the sum
1008 of |εm |πquantities and the sum of their squares
1017 are both consistent with the hypothesis that
1024 the |εm |πquantities are equal, that hypothesis
1031 is true.'' In a strong form, this principle may
1040 be stated as follows:|'{A12}|≡L|≡e|≡m|≡m|≡a |≡E|≡.|9|4|εGive
1045 n m sequences of numbers |↔by|βj|βn|↔v|4α=↓|4y|βj|β0,|4y|βj|
1050 β1,|4y|βj|β2,|4.|4.|4. for 1|4|¬E|4j|4|¬E|4m,
1053 suppose that|'{A3}!|7|uw|πlim|uc|)|.|εn|¬M|¬X|)|4(y|β1|βn|4α
1055 +↓|4y|β2|βn|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4y|βm|βn)|4|∂α=↓|4m|≤a,
1055 |4|4|;{B6}(14)|?{B6}| |uw|πlim|4sup|uc|)|.|εn|¬M|¬X|)|4(y|ur
1057 2|)1n|)|4α+↓|4y|ur2|)2n|)|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4y|ur2|)m
1057 n|))|4|L|¬E|4m|≤a|g2.>{A9}Then for each j, |πlim|ε|βn|β|¬M|β
1062 |¬X|4y|βj|βn exists and equals |≤a.|'{A12}!|9|7|πAn
1068 incredibly simple proof of this lemma is given
1076 in exercise 9.|'{A12}!|9|7Now to continue our
1083 proof of Theorem C. Let |εx|4α=↓|4x|β1x|β2|4.|4.|4.|4x|βm
1089 |πbe a |εb-|πary number, and say that |εx occurs
1098 |πat position |εp |πof the sequence if |εX|βp|βα_↓|βm|βα+↓|β
1105 1X|βp|βα_↓|βm|βα+↓|β2|4.|4.|4.|4X|βp|4α=↓|4x.
1106 |πLet |ε|≤n|βj(n) |πbe the number of occurrences
1113 of |εx |πat |πposition |εp |πwhen |εp|4|¬W|4n
1120 |πand |εp|4|πmod|4|εm|4α=↓|4j. |πLet |εy|βj|βn|4α=↓|4|≤n|βj(
1123 n)/n; |πwe wish to prove that|'{A3}|uwlim|uc|)|.|εn|¬M|¬X|)|
1129 4y|βj|βn|4α=↓|41/mb|gm.|J!(15)|;{A9}!|9|7|πFirst
1131 we know that|'{A3}|uwlim|uc|)|.|εn|¬M|¬X|)|4(y|β0|βn|4α+↓|4y
1134 |β1|βn|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4y|β(|βm|βα_↓|β1|β)|βn)|4α=↓
1134 |41/b|gm,|J!(16)|;{A9}|πsince the sequence is
1139 |εm-|πdistributed. By Lemma E and Eq. (16), the
1147 theorem will be proved if we can show that|'{A3}|uwlim|4sup|
1156 uc|)|.|εn|¬M|¬X|)|4(y|ur2|)0n|)|4α+↓|4y|ur2|)1n|)|4α+↓|4αo↓|
1156 4αo↓|4αo↓|4α+↓|4y|ur2|)(mα_↓1)n|))|4|¬E|41/mb|g2|gm.|J!(17)|
1156 ;{A9}!|9|7|πThis inequality is not obvious yet;
1163 some rather delicate maneuvering is necessary
1169 before we can prove it. Let |εq |πbe a multiple
1179 of |εm, |πand consider|'{A9}|εC(n)|4α=↓|4|↔k|uc|)0|¬Ej|¬Wm|)
1183 |1|1|↔a|(|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓|4q)|d52|)|↔s.|J!(18)|
1183 ;{A9}|πThis is the number of pairs of occurrences
1192 of |εx |πin positions |εp|β1,|4p|β2 |πwith |εn|4α_↓|4q|4|¬E|
1198 4p|β1|4|¬W|4p|β2|4|¬W|4n |πand with |εp|β2|4α_↓|4p|β1
1202 |πa multiple of |εm. |πConsider now the sum|'
1210 {A3}|εS|βN|4α=↓|4|↔k|uc|)1|¬En|¬ENα+↓q|)|4C(n).|J!(19)|;
1211 {A9}|πEach pair of occurrences of |εx |πin positions
1219 |εp|β1,|4p|β2 |πwith |εp|β1|4|¬W|4p|β2|4|¬W|4p|β1|4α+↓|4q,
1222 p|β2|4α_↓|4p|β1 |πa multiple of |εm, |πand |εp|β1|4|¬E|4N,
1229 |πis counted |εp|β1|4α+↓|4q|4α_↓|4p|β2 |πtimes
1233 in the total |εS|βN (|πnamely, when |εp|β2|4|¬W|4n|4|¬E|4p|β
1239 1|4α+↓|4q); |πand the pairs of such occurrences
1246 with |εN|4|¬W|4p|β1|4|¬W|4p|β2|4|¬W|4N|4α+↓|4q
1248 |πare counted |εN|4α+↓|4q|4α_↓|4p|β2 |πtimes.|'
1252 !|9|7Let |εd|βt(n) |πbe the number of pairs of
1260 oc urrences of |εx |πin positions |εp|β1,|4p|β2
1267 |πwith |εp|β1|4α+↓|4t|4α=↓|4p|β2|4|¬W|4n. |πThe
1270 analysis above shows that|'{A3}|ε|↔k|uc|)0|¬Wt|¬Wq/m|)|4(q|4
1274 α_↓|4mt)|4d|βm|βt(N|4α+↓|4q)|4|¬R|4S|βN|4|¬R|4|↔k|uc|)0|¬Wt|
1274 ¬Wq/m|4(q|4α_↓|4mt)|4d|βm|βt(N).|J!(20)|;{A9}|πSince
1276 the original sequence is |εq-|πdistributed,|'
1281 {A9}|uwlim|)|.|εN|¬M|¬X|)|4|(1|d2N|)|4d|βm|βt(N)|4α=↓|41/b|g
1281 2|gm|J!(21)|;{A9}|πfor all |εo|4|¬W|4t|4|¬W|4q/m,
1285 |πand therefore by (20)|'{A9}|∂|uwlim|uc|)|ε|.N|¬M|¬X|)|4|(S
1289 |βN|d2N|)|4α=↓|1|1|↔k|uc|)0|¬Wt|¬Wq/m|)|1|1(q|4α_↓|4mt)/b|g2
1289 |gm|;{A4}|h|L|βN|β|¬M|β|¬X|4S|βN|4|nα=↓|4q(q|4α_↓|4m)/2mb|g2
1290 |gm.|J!(22)>{A9}|πThis fact will prove the theorem,
1297 after some manipulation.|'|Hu*?*?{U0}{H10L12M29}|πW58320#Compu
folio 201 galley 3
1300 ter Programming!(Knuth/Addison-Wesley)!f.|4201!ch.|43!g.|43d
1301 |'{A6}!|9|7By De_nition,|'{A3}|ε2S|βN|4α=↓|4|↔k|uc|)1|¬En|¬E
1304 Nα+↓q|)|4|↔k|uc|)0|¬Ej|¬Wm|)|4{H12}({H10}(|≤n|βj(n)|4α_↓|4|≤
1304 n|βj(n|4α_↓|4q))|g2|4α_↓|4(|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓|4q)
1304 ){H12}){H10},|;{A9}|πand we can remove the unsquared
1311 terms by applying (16) to get|'{A6}{A3}|uwlim|uc|)|.|εN|¬M|¬
1317 X|)|4|(T|βN|d2N|)|4α=↓|4q(q|4α_↓|4m)/mb|g2|gm|4α+↓|4q/b|gm,|
1317 J!(23)|;{A3}|πwhere|'|εT|βN|4α=↓|4|↔k|uc|)1|¬En|¬ENα+↓q|)|4|
1319 ↔k|uc|)0|¬Ej|¬Wm|)|4{H12}({H10}|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓
1319 |4q){H12}){H10}|g2.|;{A9}!|9|7|πUsing the inequality|'
1323 {A6}|(|ε1|d2r|)|1|1|↔a|↔k|uc|)1|¬Ej|¬Er|)|1|1a|βj|↔s|g2|4|¬E
1323 |4|↔k|uc|)1|¬Ej|¬Er|)|4a|ur2|)j|)|;{A9}(|πcf.
1325 exercise 1.2.3<30), we _nd that|'{A9}|uwlim|4sup|uc|)|.|εN|¬
1330 M|¬X|)|4|↔k|uc|)0|¬Ej|¬Wm|)|4|(1|d2N(N|4α+↓|4q)|)|4|↔a|↔k|uc
1330 |)1|¬En|¬ENα+↓q|)|1|1(|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓|4q){H12}
1330 ){H10}|↔s|g2|'{A2}|¬E|4q(q|4α_↓|4m)/mb|g2|gm|4α+↓|4q/b|gm.!(
1331 24)|?{A6}|πWe also have|'{A3}|εq|≤n|βj(N)|4|¬E|4|↔k|uc|)N|¬W
1335 n|¬ENα+↓q|)|1|1|≤n|βj(n)|4α=↓|4|↔k|uc|)1|¬En|¬ENα+↓q|)|1|1{H
1335 12}({H10}|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓|4q){H12}){H10}|4|¬E|4
1335 q|≤n|βj(N|4α+↓|4q),|;{A9}|πand putting this into
1340 (24) gives|'{A3}|uwlim|4sup|uc|)|.|εN|¬M|¬X|)|4|↔k|uc|)0|¬Ej
1342 |¬Wm|)|1|1{H12}({H10}|≤n|βj(N)/N{H12}){H10}|g2|4|¬E|4(q|4α_↓
1342 |4m)/qmb|g2|gm|4α+↓|41/qb|gm.|J!(25)|;{A9}|πThis
1344 formula has been proved whenever |εq |πis a multiple
1353 of |εm, |πand if we let |εq|4|¬M|4|¬X |πwe obtain
1362 (17), completing the proof.|'!|9|7For a possibly
1369 simpler proof, see J. W. S. Cassels, |εPaci⊂c
1377 Journal of Mathematics |≡2 (1952), 555<557.|'
1383 {A12}|π!|9|7Exercises 29 and 30 illustrate the
1389 nontriviality of this theorem, and they also
1396 illustrate the fact, indicated in (25), that
1403 a |εq-|πdistributed sequence will have probabilities
1409 deviating from the true (|εm,|4m)-|πdistribution
1414 probabilities by essentially 1/|¬H|v4|εq|) |πat
1419 most. The full hypothesis of |ε|¬X-|πdistribution
1425 is necessary for the proof of the theorem.|'!|9|7As
1434 a result of Theorem C, we can prove that an |ε|¬X-|πdistribu
1444 ted sequence passes the serial test, the ``maximum
1452 of |εt'' |πtest, and the tests on subsequences
1460 mentioned in Section 3.3.2. It is not hard to
1469 show that the gap test, the poker test, and the
1479 run test are also satis_ed (see exercises 12
1487 through 14); the coupon collector's test is considerably
1495 more di∃cult to deal with, but it too is satis_ed
1505 (see exercises 15 and 16).|'{A12}!|9|7The existence
1512 of |¬X-distributed sequences of a rather simple
1519 type is guaranteed by the next theorem.|'{A12}|≡T|≡h|≡e|≡o|≡
1526 r|≡e|≡m |≡F (J. Franklin).|9|4|εThe [0,|41) sequence
1532 U|β0,|4U|β1,|4.|4.|4.|4, with|'{A9}U|βn|4α=↓|4(|≤u|gn|4|πmod
1534 |41)|J!(26)|;{A9}|εis |¬X-distributed for almost
1539 all real numbers |≤u|4|¬Q|41. That is, the set|'
1547 {A9}|¬T|≤u|4|¬G|4|≤u|4|¬Q|41 |πand (26) is not
1552 |¬X-distributed|¬Y|;{A9}|εis of measure zero.|'
1557 {A12}!|9|7|πThe proofs of this theorem and some
1564 generalizations are given in Franklin's paper
1570 quoted below.|'{A12}!|9|7Franklin has shown that
1576 |ε|≤u |πmust be a transcendental number for (26)
1584 to be |¬X-distributed. The powers (|ε|≤p|gn|4|πmod|41)
1590 have been laboriously computed for |εn|4|¬E|410000,
1596 |πusing multiple-precision arithmetic, and the
1601 most signi_cant 35 bits of each of these numbers,
1610 stored on a disk _le, have been sucessfully used
1619 as a source of uniform deviates. We have the
1628 interesting situation that, by Theorem F, the
1635 probability that the powers (|ε|≤p|gn|4|πmod|41)
1640 are |¬X-distributed is equal to 1; yet because
1648 there are uncountably many real numbers, this
1655 gives us no information as to whether the sequence
1664 is really |¬X-distributed or not. It is a fairly
1673 safe bet that nobody in our lifetimes will ever
1682 |εprove |πthat this particular sequence is |εnot
1689 |π|¬X-distributed; but it might not be. Because
1696 of these considerations, one may legitimately
1702 wonder if there is any |εexplicit |πsequence
1709 which is |¬X-distributed; i.e., |εis there an
1716 algorithm to compute real numbers U|βn for all
1724 n|4|¬R|40, such that the sequence |↔bU|βn|↔v
1730 is |¬X-distributed? |πThe answer is yes, as shown
1738 for example by the author in |εBIT |≡5 (|π1965),
1747 246<250. The sequence constructed there consists
1753 entirely of rational numbers; in fact, each number
1761 |εU|βn |πhas a terminating representation in
1767 the binary number system. Another construction
1773 of an explicit |¬X-distributed sequence, somewhat
1779 more complicated than the sequence just cited,
1786 follows from Theorem W below. See also N. M.
1795 Korobov, |εIzv. Akad. Nauk SSSR |π|≡2|≡0 (1956),
1802 649<660.|'{A12}|≡C|≡.|9|≡D|≡o|≡e|≡s |=|¬X|¬X|≡-|≡d|≡i|≡s|≡t|
1804 ≡r|≡i|≡b|≡u|≡t|≡e|≡d|4|≡α=↓|4|≡r|≡a|≡n|≡d|≡o|≡m|≡?|9|4In
1805 view of all the above theory about |¬X-distributed
1813 sequences, we can be sure of one thing: the concept
1823 of an |¬X-distributed sequence is an important
1830 one in mathematics. There is also a good deal
1839 of evidence that the following statement is a
1847 valid formulation of the intuitive idea of randomness:|'
1855 {A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|≡n |≡R|≡1|≡.|9|4|εA
1857 [0,|41) sequence is de⊂ned to be ``random'' if
1865 it is an |¬X-distributed sequence.|'{A12}|πWe
1871 have seen that sequences meeting this de_nition
1878 will satisfy all the statistical tests of Section
1886 3.3.2 and many more.|'!|9|7Let us attempt to
1894 criticize this de_nition objectively. First of
1900 all, is every ``truly random'' sequence |¬X-distributed?
1907 There are uncountably many sequences |εU|β0,|4U|β1,|4.|4.|4.
1912 |πof real numbers between zero and one. If a
1922 truly random number generator is sampled to give
1930 values |εU|β0,|4U|β1,|4.|4.|4.|4, |πany of the
1935 possible sequences may be considered equally
1941 likely, and some of the sequences (indeed, uncountably
1949 many of them) are not even equi|-distributed.
1956 On the other hand, using any reasonable de_nition
1964 of probability on this space of all possible
1972 sequences leads us to conclude that a random
1980 sequence is |¬X-distributed |εwith probability
1985 one. |πWe are therefore led to formalize Franklin's
1993 de_nition of randomness (as given at the beginning
2001 of this section) in the following way:|'{A12}|≡D|≡e|≡_|≡n|≡i
2008 |≡t|≡i|≡o|≡n |≡R|≡2|≡.|9|4|εA [0,|41) sequence
2012 |↔bU|βn|↔v is de⊂ned to be ``random'' if, whenever
2020 P is a property such that P(|↔bV|βn|↔v) holds
2028 with probability one for a sequence |↔bV|βn|↔v
2035 of independent samples of random variables from
2042 the uniform distribution, then P(|↔bU|βn|↔v)
2047 is true.|'!|9|7|πIs it perhaps possible that
2054 De_nition R1 is equivalent to De_nition R2? Let
2062 us try out some possible objections to De_nition
2070 R1, and see whether these cricicisms are valid.|'
2078 !|9|7In the _rst place, De_nition R1 deals only
2086 with limiting properties of the sequence as |εn|4|¬M|4|¬X.
2094 |πThere are |¬X-distributed sequences in which
2100 the _rst million elements are all zero; should
2108 such a sequence be considered random?|'!|9|7This
2115 objection is not very valid. If |εe |πis any
2124 positive number, there is no reason why the _rst
2133 million elements of a sequence should not all
2141 be less than |ε|≤e; |πas pointed out earlier
2149 in this section, there is no legitimate way to
2158 say if a _nite sequence is random or not. With
2168 probability one, a truly random sequence contains
2175 in_nitely many runs of a million consecutive
2182 elements less than |ε|≤e, |πso why can't this
2190 happen at the beginning of the sequence?|'!|9|7On
2198 the othe{U0}{H10L12M29}|πW58320#Computer Programming!(Knuth/
folio 204 galley 4
2200 Addison-Wesley)!f.|4204!ch.|43!g.|44d|'{A6}!|9|7Now
2202 let |εP |πbe the property that |εno |πelement
2210 of the sequence is equal to zero; again, |εP
2219 |πis true with probability one, so by De_nition
2227 R2 any sequence with a zero rlrment is not random.
2237 More generally, however, let |εX|β0 |πbe any
2244 _xed number between zero and one, and let |εP
2253 |πbe the property that no element of the sequence
2262 is equal to |εx|β0; |πDe_nition R2 now says that
2271 no random sequence may contain the element |εx|β0*3
2279 |πWe can now prove that |εno sequence satis⊂es
2287 the condition of De⊂nition R2. (|πFor if |εU|β0,|4U|β1,|4.|4
2294 .|4. |πis such a sequence, take |εx|β0|4α=↓|4U|β0.)|'
2301 !|9|7|πTherefore if R1 is too weak a de_nition,
2309 R2 is certainly too strong. The ``right'' de_nition
2317 must be less strict than R2. We have not really
2327 shown that R1 is too weak, however, so let us
2337 continue to attack it some more. As mentioned
2345 above, an |¬X-distributed sequence of |εrational
2351 |πnumbers has been constructed. (Indeed, this
2357 is not so surprising: see exercise 18.) Almost
2365 all real numbers are irrational; perhaps we should
2373 insist that|'{A9}Pr(|εU|βn |πis rational)|4α=↓|40|;
2378 {A9}for a random sequence.|'!|9|7Note that the
2385 de_nition of equidistribution says that Pr(|εu|4|¬E|4U|βn|4|
2390 ¬W|4v)|4α=↓|4v|4α_↓|4u. |πThere is an obvious
2395 way to generalize this de_nition, using measure
2402 theory: ::If |εS|4|↔Y|4[0,|41) |πis a set of
2409 measure |ε|≤m, |πthen|'{A9}Pr(|εU|βn|4|¬A|4S)|4α=↓|4|≤m,|J!(
2412 27)|;{A9}|πfor all random sequences |↔b|εU|βn|↔v.''
2418 |πIn particular, if |εS |πis the set of rationals,
2427 it has measure zero, so no sequence of rational
2436 numbers is equi|-distributed in this generalized
2442 sense. It is reasonable to expect that Theorem
2450 B could be extended to Lebesgue integration instead
2458 of Riemann integration, if property (27) is stipulated.
2466 However, once again we _nd that de_nition (27)
2474 is too strict, for |εno |πsequence satis_es that
2482 property*3 If |εU|β0,|4U|β1,|4.|4.|4. |πis any
2487 sequence, the set |εS|4α=↓|4|¬TU|β0,|4U|β1,|4.|4.|4.|¬Y
2491 |πis of measure zero, yet Pr(|εU|βn|4|¬A|4S)|4α=↓|41.
2497 |πThus, by the force of the same argument we
2506 used to exclude rationals from random sequences,
2513 we can exclude all random sequences.|'!|9|7So
2520 far De_nition R1 has proved to be defensible.
2528 There are, however, some quite valid objections
2535 to it. For example, if we have a random sequence
2545 in the intuitive sense, the in_nite subsequence|'
2552 {A9}|εU|β0, U|β1, U|β4, U|β9, U|βn|l2,|4.|4.|4.|J!(28)|;
2557 {A9}|πshould also be a random sequence. This
2564 is not always true for an |¬X-distributed sequence.
2572 (In fact, if we take any |¬X-distributed sequence
2580 and set |εU|βn|l2|4|¬L|40 |πfor all |εn, |πthe
2587 counts |ε|≤n|βk(n) |πwhich appear in the test
2594 of |εk-|πdistributivity are changed by at most
2601 |¬H|v4|εn|), |πso the limits of the ratios |ε|≤n|βk(n)/n
2609 |πremain unchanged.) Therefore R1 de_nitely fails
2615 to satisfy this randomness criterion.|'!|9|7Perhaps
2621 we should strengthen R1 as follows:|'{A12}|≡D|≡e|≡_|≡n|≡i|≡t
2627 |≡i|≡o|≡n |≡R|≡3|≡.|9|4|εA [0,|41) sequence is
2632 said to be ``random'' if every in⊂nite subsequence
2640 is |¬X-distributed.|'{A12}|πBut once again we
2646 _nd this de_nition is too strict. If |↔b|εU|βn|↔v
2654 |πis any equi|-distributed sequence, it has a
2661 monotonic subsequence with |εU|βs|m0|4|¬W|4U|βs|m1|4|¬W|4U|β
2664 s|m2|4|¬W|4αo↓|4αo↓|4αo↓|4.|'!|9|7|πThe secret
2667 is to restrict the subsequences so that they
2675 could be de_ned by a man who does not look at
2686 |εU|βn |πbefore he decides whether or not it
2694 is to be in the subsequence. The following de_nition
2703 now suggests itself:|'{A12}|≡D|≡e≡_|≡n|≡i|≡t|≡i|≡o|≡n
2707 |≡R|≡4|≡.|9|4|εA [0,|41) sequence |↔bU|βn|↔v
2711 is said to be ``random'' if, for every e∩ective
2720 algorithm which speci⊂es an in⊂nite sequence
2726 of distinct nonnegative integers s|βn for n|4|¬R|40,
2733 the subsequence U|βs|m0,|4U|βs|m1,|4.|4.|4. corresponding
2737 to this algorithm is |¬X-distributed.|'{A12}|π!|9|7The
2743 algorithms referred to in this de_nition are
2750 e=ective procedures which compute |εs|βn, |πgiven
2756 |εn. (|πSee Section 1.1.) Thus, for example,
2763 the sequence |↔b|ε|≤p|gn|4|πmod|41|↔v will |εnot
2768 |πsatisfy R4, since it is either not equidistributed
2776 or there is an e=ective algorithm which determines
2784 an in_nite subsequence |εs|βn |πwith (|ε|≤p|gs|r0|4|πmod|41)
2789 |4|¬W|4(|ε|≤p|gs|r1|4|πmod|41)|4|¬W|4αo↓|4αo↓|4αo↓|4.
2790 Similarly, |εno explicitly de⊂ned sequence can
2796 satisfy De⊂nition R|*/|↔M; |\|πthis is appropriate,
2802 if we agree that no explicitly de_ned sequence
2810 can really be random. It is quite likely, however,
2819 that the sequence (|ε|≤u|gn|4|πmod|41|↔v will
2824 satisfy De_nition R4, for almost all real numbers
2832 |ε|≤u|4|¬Q|41; |πthis is no contradiction, since
2838 almost all |ε|≤u |πare uncomputable by algorithms.
2845 The following facts are known, for example: (i)
2853 The sequence |↔b|ε|≤u|gn|4|πmod|41|↔v satis_es
2857 De_nition R4 for almost all real |ε|≤u|4|¬Q|41,
2864 |πif ``|¬X-distributed'' is replaced by ``1-distributed.''
2870 This theorem was proved by J. F. Koksma, |εCompositio
2879 Mathematica |π|≡2 (1935), 250<258. (ii) The particular
2886 sequence |↔b|ε|≤u|gs|g(|gn|g)|4|πmod|41|↔v is
2889 |¬X-distributed for almost all real |ε|≤u|4|¬Q|41,
2895 |πif |↔b|εs(n)|↔v |πis a sequence of integers
2902 for which |εs(n|4α+↓|41)|4α_↓|4s(n)|4|¬M|4|¬X
2905 |πas |εn|4|¬M|4|¬X. |πFor example, we could have
2912 |εs(n)|4α=↓|4n|g2, |πor |εs(n)|4α=↓|4|"ln|4|πlog|4|εn|↔L.|'
2915 !|9|7|πDe_nition R4 is much stronger than De_nition
2922 R1; but it is still reasonable to claim that
2931 De_nition R4 is too weak. For example, let |↔b|εU|βn|↔v
2940 |πbe a truly random sequence, and de_ne the subsequence
2949 |↔b|εU|βs|mn|↔v |πby the following rules: |εs|β0|4α=↓|40,
2955 |πand (for |εn|4|¬Q|4O) s|βn |πis the smallest
2962 integer |→|¬R|εn |πfor which |εU|βs|mn|βα_↓|β1,
2967 U|βs|mn|βα_↓|β2,|4.|4.|4.|4, U|βs|mn|βα_↓|βn
2969 |πare all less than |f1|d32|). Thus we are considering
2978 the subsequence of values following the _rst
2985 consecutive run of |εn |πvalues less than |f1|d32|).
2993 Suppose that ``|εU|βn|4|¬W|4|f1|d32|)'' |πcorresponds
2997 to the value ``heads'' in the ⊗ipping of a coin.
3007 Gamblers tend to feel that a long run of ``heads''
3017 makes the opposite condition, ``tails,'' more
3023 probable, assuming a true coin is being used;
3031 and the subsequence |ε|↔bU|βs|mn|↔v |πjust de_ned
3037 corresponds to a gambling system for a man who
3046 places his |εn|πth bet on the coin toss following
3055 the _rst run of |εn |πconsecutive ``heads.''
3062 The gambler may think that Pr(|εU|βs|mn|4|¬R|4|f1|d32|))
3068 |πis more than |f1|d32|), but of course in a
3077 truly random sequence, |ε|↔bU|βs|mn|↔v |πwill
3082 be completely random. No gambling system will
3089 ever able to beat the odds*3 De_nition R4 says
3098 nothing about subsequences formed according to
3104 such a gambling system, and so apparently we
3112 need something more.|'!|9|7Let us de_ne a ``subsequence
3120 rule'' |λR as an in_nite sequence of functions
3128 |ε|↔bf|βn(x|β1,|4.|4.|4.|4,|4x|βn)|↔v |πwhere,
3130 for |εn|4|¬R|40, f|βn |πis a function of |εn
3138 |πvariables, and the value of |εf|βn(x|β1,|4.|4.|4.|4,|4x|βn
3143 ) |πis either 0 or 1. Here |εx|β1,|4.|4.|4.|4,|4x|βn
3151 |πare elements of some set |εS. (|πThus, in particular,
3160 |εf|β0 |πis a constant function, either 0 or
3168 1.) A subsequence rule |λR de_nes a subsequence
3176 of any in_nite sequence |↔b|εX|βn|↔v |πof elements
3183 of |εS |πas follows: |εThe n|πth |εterm X|βn
3191 is in the subsequence |↔bX|βn|↔v|λR if and only
3199 if f|βn(X|β0, X|β1,|4.|4.|4.|4,|4X|βn|βα_↓|β1)|4α=↓|41.
3202 |πNote that the subsequence |ε|↔bX|βn|↔v|λR |πthus
3208 de_ned is not necessarily in_nite, and it may
3216 in fact be the null subsequence.|'!|9|7The ``gambler's
3224 subsequence'' which was described above corresponds
3230 to the following subsequence rule: ``|εf|β0|4α=↓|41;
3236 |πand for |εn|4|¬Q|40, f|βn(x|β1,|4.|4.|4.|4,|4x|βn)|4α=↓|41
3239 |πif and only if there is some |εk,|40|4|¬W|4k|4|¬E|4n,
3248 |πsuch that |εx|βm|4|¬W|4|f1|d32|), x|βm|βα_↓|β1|4|¬W|4|f1|d
3251 32|),|4.|4.|4.|4, x|βm|βα_↓|βk|βα+↓|β1|4|¬W|4|f1|d32|),
3253 |πwhen |εm|4α=↓|4n |πbut not when |εk|4|¬E|4m|4|¬W|4n.''|'
3259 !|9|7|πA subsequence rule |λR is said to be |εcomputable
3268 |πif there is an e=ective algorithm which determines
3276 the value of |εf|βn(x|β1,|4.|4.|4.|4,|4x|βn),
3280 |πwhen |εn,|4x|β1,|4.|4.|4.|4,|4x|βn |πare given
3284 as input. In a de_nition of randomness, we should
3293 restrict ourselves to computable subsequence
3298 rules, or else we obtain a de_nition like R3
3307 above, which is too strong. E=ective algorithms
3314 cannot deal nicely with arbitrary real numbers
3321 as inputs; for example, if a real number |εx
3330 |πis speci_ed by an in_nite radix-10 expansion,
3337 there is no algorithm to determine if |εx |πis
3347 |→|¬W|f1|d33|) or not, since all digits of the
3355 number 0.333|4.|4.|4. would have to be examined.
3362 Therefore computable subsequence rules do not
3368 apply to all [0,|41) sequences, and it is convenient
3377 to base our next de_nition on |εb-|πary sequences:|'
3385 {A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|≡n |≡R|≡5|≡.|9|4|εA
3387 b-ary sequence is said to be ``random'' if every
3396 in⊂nite subsequence de⊂ned by a computable subsequence
3403 rule is |*/|↔O|\-distributed.|'!|9|7A [0,|41)
3408 sequence |↔bU|βn|↔v is said to be ``random''
3415 if the b-ary sequence |↔b|"lbU|βn|"L|↔v is ``random''
3422 for all integers b|4|¬R|42.|'|Hu{U0}{H10L12M29}|πW58320#Comp
folio 206 galley 5
3426 uter Programming!(Knuth/Addison-Wesley)!f.|4206!ch.|43!g.|45
3427 d|'{A6}{A6}!|9|7Note that De_nition R5 says only
3434 ``1-distributed,'' not ``|¬X-distributed.'' It
3438 is interesting to note that this may be done
3447 without loss of generality. for, we may de_ne
3455 an obviously computable subsequence rule |λR(|εa|β1|4.|4.|4.
3460 |4a|βk) |πas follows for any |εb-|πary number
3467 |εa|β1|4.|4.|4.|4a|βk: |πLet |εf|βn(x|β1,|4.|4.|4.|4,|4x|βn)
3469 |4α=↓|41 |πif and only if |εn|4|¬R|4k|4α_↓|41
3475 |πand |εx|βn|βα_↓|βk|βα+↓|β1|4α=↓|4a|β1,|4.|4.|4.|4,
3477 x|βn|βα_↓|β1|4α=↓|4a|βk|βα_↓|β1, x|βn|4α=↓|4a|βk.
3479 |πNow if |ε|↔bX|βn|↔v |πis a |εk-|πdistributed
3485 |εb-|πary sequence, this rule |λR(|εa|β1|4.|4.|4.|4a|βk)#|πw
3489 hich selects the subsequence consisting of those
3496 terms just following an occurrence of |εa|β1|4.|4.|4.|4a|βk#
3502 |πde_nes an in_nite subsequence; and if this
3509 subsequence is 1-distributed, each of the |ε(k|4α+↓|41)-|πtu
3515 ples |εa|β1|4.|4.|4.|4a|βka|βk|βα+↓|β1 |πfor
3518 0|4|¬E|4|εa|βk|βα+↓|β1|4|¬W|4b |πoccurs with
3521 probability |ε1/b|gk|gα+↓|g1 |πin |↔b|εX|βn|↔v.
3525 |πThus we can prove that a sequence satisfying
3533 De_nition R5 is |εk-|πdistributed for all |εk,
3540 |πby induction on |εk. |πSimilarly, by considering
3547 the ``composition'' of subsequence rules#if |λR|β1
3553 de_nes an in_nite subsequence |↔b|εX|βn|↔v|λR|β1,
3558 |πthen we can de_ne |λR|β1|λR|β2 to be the subsequence
3567 rule for which |↔b|εX|βn|↔v|λR|β1|λR|β2|4α=↓|4(|↔bX|βn|↔v|λR
3570 |β1)|λR|β2#|πwe _nd that all subsequences considered
3576 in De_nition R5 are |¬X-distributed. (See exercise
3583 32.)|'!|9|7The fact that |¬X-distribution comes
3589 out of De_nition R5 as a very special case is
3599 encouraging, and it is a good indication that
3607 we may at last have found the de_nition of randomness
3617 which we have been seeking. But alas, there still
3626 is a problem*3 It is not clear that sequences
3635 satisfying De_nition R5 must satisfy De_nition
3641 4. The ``computable subsequence rules'' we have
3648 just speci_ed always enumerate subsequences |↔b|εX|βs|mn|↔v
3654 |πfor which |εs|β0|4|¬W|4s|β1|4|¬W|4αo↓|4αo↓|4αo↓|4,
3657 |πbut |ε|↔bs|βn|↔v |πdoes not have to be monotone
3665 in R4; it must only satisfy the condition |εs|βn|4|=|↔6α=↓|4
3673 s|βm |πfor |εn|4|=|↔6α=↓|4m.|'!|9|7|πTo meet
3678 this objection, we may combine De_nitions R4
3685 and R5 as follows:|'{A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|≡n
3690 |≡R|≡6|≡.|9|4|εA b-ary sequence |↔bX|βn|↔v is
3695 said to be ``random'' if, for every e∩ective
3703 algorithm which speci⊂es an in⊂nite sequence
3709 of distinct nonnegative integers |↔bs|βn|↔v as
3715 a function of n and the values of X|βs|m0,|4.|4.|4.|4,|4X|βs
3723 |mn|mα_↓|m1, the subsequence |↔bX|βs|mn|↔v corresponding
3728 to this algorithm is ``random'' in the sense
3736 of De⊂nition R|*/|↔C|\.|'!|9|7A [0,|41) sequence
3742 |↔bU|βn|↔v is said to be ``random'' if the b-ary
3751 sequence |↔b|"lbU|βn|"L|↔v is ``random'' for
3756 all integers b|4|¬R|42.|'{A12}|π!|9|7The author
3761 contendsα/↓ that this de_nition surely meets
3767 all reasonable philosophical requirements for
3772 randomness, and so it provides an answer to the
3781 principal question posed in this section.|'{A2}######|'
3788 {H8L10}!α/↓|4At least, he felt that way when
3795 originally preparing the material for this section.|'
3802 {A12}{H10L12}|≡D|≡.|9|≡E|≡x|≡i|≡s|≡t|≡e|≡n|≡c|≡e
3803 |≡o|≡f |≡r|≡a|≡n|≡d|≡o|≡m |≡s|≡e|≡q|≡u|≡e|≡n|≡c|≡e|≡s|≡.|9|4
3805 We have seen that De_nition R3 is too strong,
3814 in the sense that no sequences could exist satisfying
3823 that de_nition; and the formulation of De_nitions
3830 R4, R5, and R6 above was carried out in an attempt
3841 to recapture the essential characteristics of
3847 De_nition R3. In order to show that De_nition
3855 R6 is not overly restrictive, it is still necessary
3864 for us to prove that sequences satisfying all
3872 these conditions exist. Intuitively, we feel
3878 quite sure that such sequences exist, because
3885 we believe that a truly random sequence exists
3893 and satis_es De_nition R6; but a proof is really
3902 necessary to show that the de_nition is consistent.|'
3910 !|9|7An interesting method for constructing sequences
3916 satisfying De_nition R5 has been given by A.
3924 Wald. The construction starts with a very simple
3932 1-distributed sequence:|'{A12}|≡L|≡e|≡m|≡m|≡a
3935 |≡T|≡.|9|4|εLet the sequence of real numbers
3941 |↔b|εV|βn|↔v be de⊂ned in terms of the binary
3949 system as follows|*/:|\|'V|β0|4|∂α=↓|40,!!V|β1|4α=↓|4.1,!!V|β
3952 2|4α=↓|4.01,!!V|β3|4α=↓|4.11,!!V|β4|4α=↓|4.001,!!.|4.|4.|;
3953 {A4}| V|βn|4|Lα=↓|4.c|βr|4.|4.|4.|4c|β11!!|πif!!|εn|4α=↓|42|
3953 gr|4α+↓|4c|β12|gr|gα_↓|g1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|βr.|J!
3953 (29)>{A9}Let I|βb|m1|1|β.|1|β.|1|β.|1b|mr denote
3957 the set of all real numbers in [0,|41) whose
3966 binary representation begins with 0.b|β1|4.|4.|4.|4b|βr|*/;|\
3970 thus|'{A9}I|ur|)b|β1|1|1.|1|1.|1|1.|1|1b|βr|)|4α=↓|4[0.b|β1
3972 |4.|4.|4.|4b|βr, o.b|β1|4.|4.|4.|4b|βr|4α+↓|42|gα_↓|gr).|J!(
3973 30)|;{A9}Then if |≤n(n) denotes the number of
3981 V|βk in I|βb|m1|1|β.|1|β.|1|β.|1|βb|mr for 0|4|¬E|4k|4|¬W|4n
3985 , we have|'{A9}|¬G|≤n(n)/n|4α_↓|42|gα_↓|gr|¬G|4|¬E|41/n.|J!(
3988 31)|;{A9}Proof.|9|4|πSince |ε|≤n(n) |πis the
3993 number of |εk |πfor which |εk|4|πmod|4|ε2|gr|4α=↓|4b|βr|4.|4
3998 .|4.|4b|β1, |πwe have |ε|≤n(n)|4α=↓|4t |πor |εt|4α+↓|41
4004 |πwhen |"l|εn/2|gr|"L|4α=↓|4t. |πHence |¬G|ε|≤n(n)|4α_↓|4n/2
4007 |gr|¬G|4|¬E|41.|'{A12}!|9|7|πIt follows from
4011 (31) that the sequence |↔b|"l|ε2|grV|βn|"L|↔v
4016 |πis an equidistributed 2|ε|gr-|πary sequence;
4021 hence by Theorem A, |↔b|εV|βn|↔v |πis an equidistributed
4029 [0,|41) sequence. Indeed, it is pretty clear
4036 that |↔b|εV|βn|↔v |πis about as equidistributed
4042 as a [0,|41) sequence can be*3 (For further discussion
4051 of this and related sequences, see J. C. van
4060 der Corput, |εProc. Koninklijke Nederlandse Akademie
4066 van Wetenschappen |≡3|≡8 (1935), 813<821, 1058<1066;
4072 |πJ. H. Halton, |εNumerische Mathematik |π|≡2
4078 (1960), 84<90, 196.)|'!|9|7Now let |λR|β1,|4|λR|β2,|4.|4.|4.
4083 be in_nitely many subsequence rules; we would
4091 like to _nd a sequence |↔b|εU|βn|↔v |πfor which
4099 all the in_nite subsequences |↔b|εU|βn|↔v|λR|βj
4104 |πare equidistributed.|'{A12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m
4107 |≡W (|εWald sequence).|9|4|πGiven an in_nite
4112 set of subsequence rules |λR|β1,|4|λR|β2,|4.|4.|4.|4,
4117 which de_ne subsequences of [0,|41) sequences
4123 of |εrational |πnumbers, this procedure de_nes
4129 a [0,|41) sequence |↔b|εU|βn|↔v. |πThe computation
4135 involves in_nitely many auxiliary variables |εC[a|β1,|4.|4.|
4140 4.|4,|4a|βr] |πwhere |εr|4|¬R|41 |πand where
4145 |εa|βj|4α=↓|40 |πor 1 for 1|4|¬E|4|εj|4|¬E|4r.
4150 |πThese variables are initially all zero.|'{A3}|π|≡W|≡1|≡.|9
4156 [Initialize |εn.] |πSet |εn|4|¬L|40.|'{A3}|π|≡W|≡2|≡.|9[Init
4160 ialize |εr.] |πSet |εr|4|¬L|41.|'{A3}|π|≡W|≡3|≡.|9[Test
4165 |λR|ε|βr.] |πIf the element |εU|βn |πis to be
4173 in the subsequence de_ned by |λR|ε|βr, |πbased
4180 on the values of |εU|βk |πfor 0|4|¬E|4|εk|4|¬W|4n,
4187 |πset |εa|βr|4|¬L|41; |πotherwise set |εa|βr|4|¬L|40.|'
4192 {A3}|π|≡W|≡4|≡.|9[|εB[a|β1,|4.|4.|4.|4,|4a|βr]
4193 |πfull?] If |εC[a|β1,|4.|4.|4.|4,|4a|βr]|4|¬W|43|4αo↓|44|gr|
4195 gα_↓|g1, |πgo to W6.|'{A3}|≡W|≡5|≡.|9[Increase
4200 |εr.] |πSet |εr|4|¬L|4r|4α+↓|41 |πand return
4205 to W3.|'{A3}|≡W|≡6|≡.|9[Set |εU|βn.] |πIncrease
4210 |εC[a|β1,|4.|4.|4.|4,|4a|βr] |πby 1 and let |εk
4216 |πbe the new value of |εC[a|β1,|4.|4.|4.|4,|4a|βr].
4222 |πSet |εU|βn|4|¬L|4V|βk, |πwhere |εV|βk |πis
4227 de_ned in Lemma T above.|'{A3}|≡W|≡7|≡.|9[Advance
4233 |εn.] |πIncrease |εn |πby 1 and return to W2.|'
4242 {A3}{A9}!|9|7Strictly speaking, this is not an
4248 algorithm, since it doesn't terminate; it would
4255 of course be easy to modify the procedure to
4264 stop when |εn |πreaches a given value. The reader
4273 will _nd it easier to grasp the idea of the construction
4284 if he tries it by hand, replacing the number
4293 3|4αo↓|44|ε|gr|gα_↓|g1 |πof step W4 by 2|ε|gr
4299 |πduring this experiment.|'!|9|7Algorithm W is
4305 not meant to be a practical source of random
4314 numbers; it is intended to serve only a theoretical
4323 purpose:|'{A12}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡W|≡.|9|4|εLet
4326 U|βn be the sequence of rational numbers de⊂ned
4334 by Algorithm W, and let k be a positive integer.
4344 If the subsequence |↔bU|βn|↔v|λR|βk is in⊂nite,
4350 it is |*/|↔O|\-distributed.|'{A12}Proof.|9|4|πLet
4354 |εA[a|β1,|4.|4.|4.|4,|4a|βr] |πdenote the (possibly
4358 empty) subsequence of |↔b|εU|βn|↔v |πcontaining
4363 precisely those elements |εU|βn |πwhich, for
4369 all |εj, 1|4|¬E|4j|4|¬E|4r, |πbelong to subsequence
4375 |ε|↔bU|βn|↔v|λR|βj |πif |εa|βj|4α=↓|41 |πand
4379 do not belong to subsequence |↔b|εU|βn|↔v|λR|βj
4385 |πif |εa|βj|4α=↓|40.|'!|9|7|πIt su∃ces to prove,
4391 for all |εr|4|¬R|41 |πand all pairs of binary
4399 numbers |εa|β1|4.|4.|4.|4a|βr |πand |εb|β1|4.|4.|4.|4b|βr,
4403 |πthat Pr(|εU|βn|4|¬A|4I|βb|m1|1|β.|1|β.|1|β.|1|βb|mr)≥|4α=↓
4404 |42|gα_↓|gr |πwith respect to the subsequence
4410 |εA[a|β1,|4.|4.|4.|4,|4a|βr], |πwhenever the
4413 latter is in_nite. [See Eq. (30).] For if |εr|4|¬R|4k,
4422 |πthe in_nite sequence |↔b|εU|βn|↔v|λR|βk |πis
4427 the _nite union of the disjoint subsequences
4434 |εA[a|β1,|4.|4.|4.|4,|4a|βr] |πfor |εa|βk|4α=↓|41
4437 |πand |εa|βj|4α=↓|40 |πor 1 for 1|4|¬E|4|εj|4|¬E|4r,
4443 j|4|=|↔6α=↓|4k; |πand it follows that Pr(|εU|βn|4|¬A|4I|βb|m
4448 1|1|β.|1|β.|1|β.|1|βb|mr)|4α=↓|42|gα_↓|gr |πwith
4450 respect to |ε|↔bU|βn|↔v|λR|βk. (|πSee exercise
4455 33.) This is enough to show that the sequence
4464 is 1-distributed, by Theorem A.|'|Hu{U0}{H10L12M29}|πW58320#
folio 209 galley 6
4469 Computer Programming!(Knuth/Addison-Wesley)!f.|4209!ch.|43!g
4470 .|46d|'{A6}!|9|7Let |εB[a|β1,|4.|4.|4.|4,|4a|βr]
4473 |πdenote the subsequence of |ε|↔bU|βn|↔v |πwhich
4479 consists of the values for those |εn |πin which
4488 |εC[a|β1,|4.|4.|4.|4,|4a|βr] |πis increased by
4492 one in step W6 of the algorithm. By the algorithm,
4502 |εB[a|β1,|4.|4.|4.|4,|4a|βr] |πis a _nite sequence
4507 with at most 3|4αo↓|44|ε|gr|gα_↓|g1 |πelements.
4512 All but a _nite number of the members of |εA[a|β1,|4.|4.|4.|
4521 4,|4a|βr] |πcome from the subsequences |εB[a|β1,|4.|4.|4.|4,
4526 |4a|βr,|4.|4.|4.|4,|4a|βt], |πwhere |εa|βj|4α=↓|40
4529 |πor 1 for |εr|4|¬W|4j|4|¬E|4t.|'!|9|7|πNow assume
4535 that |εA[a|β1,|4.|4.|4.|4,|4a|βr] |πis in_nite,
4539 and let |εA[a|β1,|4.|4.|4.|4,|4a|βr]|4α=↓|4|↔bU|βs|mn|↔v
4542 |πwhere |εs|β0|4|¬W|4s|β1|4|¬W|4s|β2|4|¬E|4αo↓|4αo↓|4αo↓|4.
4544 |πIf |εN |πis a large integer, with |ε4|gr|4|¬E|44|gq|4|¬W|4
4551 N|4|¬E|44|gq|gα+↓|g1, |πit follows that the number
4557 of values of |εk|4|¬W|4N |πfor which |εU|βs|mk
4564 |πis in |εI|βb|m1|1|β.|1|β.|1|β.|1|βb|mr |πis
4568 (except for _nitely many elements at the beginning
4576 of the subsequence)|'{A9}|ε|≤n(N)|4α=↓|4|≤n(N|β1)|4α+↓|4αo↓|
4579 4αo↓|4αo↓|4α+↓|4|≤n(N|βm).|;{A9}|πHere |εm |πis
4583 the number of subsequences |εB[a|β1,|4.|4.|4.|4,|4a|βt]
4588 |πlisted above in which |εU|βs|mk |πappears for
4595 some |εk|4|¬W|4N; N|βj |πis the number of values
4603 of |εk |πwith |εU|βs|mk |πin the corresponding
4610 subsequence; and |ε|≤n(N|βj) |πis the number
4616 of such values which are also in |εI|βb|m1|1|β.|1|β.|1|β.|1|
4623 βb|mr. |πTherefore by Lemma T,|'{A9}|ε|¬G|≤n(N)|4α_↓|42|gα_↓
4628 |grN|¬G|4|∂α=↓|4|¬G|≤n(N|β1)|4α_↓|42|gα_↓|grN|β1|4α+↓|4αo↓|4
4628 αo↓|4αo↓|4α+↓|4|≤n(N|βm)|4α_↓|42|gα_↓|grN|βm|¬G|9|;
4629 {A4}|L|¬E|4|¬G|≤n(N|β1)|4α_↓|42|gα_↓|grN|β1|¬G|4α+↓|4αo↓|4αo
4629 ↓|4αo↓|4α+↓|4|¬G|≤n(N|βm)|4α_↓|42|gα_↓|grN|βm|¬G>
4630 {A4}|L|¬E|4m|4|¬E|41|4α+↓|42|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|42|gq|
4630 gα_↓|gr|gα+↓|g1|4|¬W|42|gq|gα+↓|g1.>{A9}|πThe
4632 inequality on |εm |πfollows here from the fact
4640 that, by our choice of |εN, U|βs|mN |πis in |εB[a|β1,|4.|4.|
4649 4.|4,|4a|βt] |πfor some |εt|4|¬E|4q|4α+↓|41.|'
4653 !|9|7|πTherefore|'{A3}|ε|¬G|≤n(N)/N|4α_↓|42|gα_↓|gr|¬G|4|¬E|
4654 42|gq|gα+↓|g1/N|4|¬W|42/|¬H|v4N|).!|9|;{A9}!|9|7|πTo
4656 show _nally that sequences satisfying De_nition
4662 R5 exist, we note _rst that if |ε|↔bU|βn|↔v |πis
4671 a [0,|41) sequence of rational numbers and if
4679 |λR is a computable subsequence rule for a |εb-|πary
4688 sequence, we can make |λR into a computable subsequence
4697 rule rule |λR|¬S |πfor |ε|¬BU|βn|¬V |πby letting
4704 |εf|ur|↔0|)n|)(x|β1,|4.|4.|4.|4,|4x|βn) |πin
4706 |λR|¬S equal |εf|βn(|"lbx|β1|"L,|4.|4.|4.|4,
4709 |"lbx|βn|"L) |πin |λR. If the sequence |ε|↔bU|βn|↔v|λR|¬S
4716 |πis equidistributed, so is the sequence |↔b|"l|εbU|βn|"L|↔v
4722 |λR. |πNow the set of all computable subsequence
4730 rules for |εb-|πary sequences, for all values
4737 of |εb, |πis countable (since only countably
4744 many e=ective algorithms are possible), so they
4751 may be listed in some sequence |λR|β1,|4|λR|β2,|4.|4.|4.|4;
4758 therefore Algorithm W de_nes a [0,|41) sequence
4765 which is random in the sense of De_nition R5.|'
4774 !|9|7This brings us to a somewhat paradoxical
4781 situation. As we mentioned earlier, no e=ective
4788 algorithm can de_ne a sequence which satis_es
4795 De_nition R4, and for the same reason there is
4804 no e=ective algorithm which de_nes a sequence
4811 satisfying De_nition R5. A proof of the existence
4819 of such random sequences is necessarily nonconstructive;
4826 how then can Algorithm W construct such a sequence?|'
4835 !|9|7There is no contradiction here; we have
4842 merely stumbled on the fact that the set of all
4852 e=ective algorithms cannot be enumerated by an
4859 e=ective algorithm. In other words, there is
4866 no e=ective algorithm to select the |εj|πth computable
4874 subsequence rule |ε|λR|βj; |πthis happens because
4880 there is no e=ective algorithm to determine if
4888 a computational method ever terminates. (We shall
4895 return to this topic in Chapter 11.) Important
4903 large classes of algorithms |εcan |πbe systematically
4910 enumerated; thus, for example, Algorithm W shows
4917 that is possible to construct, with an e=ective
4925 algorithm, a sequence which satis_es De_nition
4931 R5 if we restrict consideration to subsequence
4938 rules which are ``primitive recursive.''|'!|9|7By
4944 modifying step W6 of Algorithm W, so that it
4953 sets |εU|βn|4|¬L|4V|βk|βα+↓|βt |πinstead of |εV|βk,
4958 |πwhere |εt |πis any nonnegative integer depending
4965 on |εa|β1,|4.|4.|4.|4,|4a|βr, |πwe can show that
4971 are |εuncountably |πmany [0,|41) sequences satisfying
4977 De_nition R5.|'!|9|7The following theorem shows
4983 still another way to prove the existence of uncountably
4992 many random sequences, using a less direct argument
5000 based on measure theory, even if the strong de_nition
5009 R6 is used:|'{A12}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡M|≡.|9|4|εLet
5014 the real number x,|40|4|¬E|4x|4|¬W|41, correspond
5019 to the binary sequence |↔bX|βn|↔v if the binary
5027 representation of x is 0.X|β0X|β1|4.|4.|4.|4.
5032 Under this correspondence, almost all x correspond
5039 to binary sequences which are random in the sense
5048 of De⊂nition R|*/|↔o|\. (|πIn other words, the
5055 set of all real |εx |πwhich correspond to a binary
5065 sequence which is nonrandom by De_nition R6 has
5073 measure zero.)|'{A12}|εProof.|9|4|πLet |λS be
5078 an e=ective algorithm which determines an in_nite
5085 sequence of distinct nonnegative integers |↔b|εs|βn|↔v,
5091 |πwhere the choice of |εs|βn |πdepends only on
5099 |εn |πand |εX|βs|mk |πfor 0|4|¬E|4|εk|4|¬W|4n;
5104 |πand let |λR be a computable subsequence rule.
5112 Then any binary sequence |ε|↔bX|βn|↔v |πleads
5118 to a subsequence |ε|↔bX|βs|mn|↔v|λR, |πand De_nition
5124 R6 says this subsequence must either be _nite
5132 or 1-distributed. It su∃ces to prove that |εfor
5140 ⊂xed |λR and |λS the set N(|λr,|4|λS) of all
5149 real x corresponding to |↔bX|βn|↔v, such that
5156 |↔bX|βs|mn|↔v|λR is in⊂nite and not |*/|↔O|\-distributed,
5162 has measure zero. |πFor |εx |πhas a nonrandom
5170 binary representation if and only if |εx |πis
5178 in |↔e|4|εN(|λR,|4|λS), |πtaken over the countably
5184 many choices of |λR |πand |λS.|'!|9|7Therefore
5191 let |λR and |λS be _xed. Consider the set |εT(a|β1a|β2|4.|4.
5200 |4.|4a|βr) |πde_ned for all binary numbers |εa|β1a|β2|4.|4.|
5206 4.|4a|βr |πas the set of all |εx |πcorresponding
5214 to |ε|↔bX|βn|↔v, |πsuch that |ε|↔bX|βs|mn|↔v|λ9
5219 |πhas |ε|→|¬Rr |πelements whose _rst |εr |πelements
5226 are respectively equal to |εa|β1,|4a|β2,|4.|4.|4.|4,|4a|βr.
5231 |πOur _rst result is that|'{A9}|εT(a|β1a|β2|4.|4.|4.|4a|βr)!
5236 !|πhas measure!!|ε|→|¬E2|gα_↓|gr.|J!(32)|;{A9}|πTo
5239 prove this, we start by observing that |εT(a|β1a|β2|4.|4.|4.
5246 |4a|βr) |πis a measurable set: Each element of
5254 |εT(a|β1a|β2|4.|4.|4.|4a|βr) |πis a real number
5259 |εx|4α=↓|40.X|β0X|β1|4.|4.|4.|4|πfor which there
5262 exists an integer |εm |πsuch that algorithm |λS
5270 determines distinct values |εs|β0,|4s|β1,|4.|4.|4.|4,|4s|βm,
5273 |πand rule |λR determines a subsequence of |εX|βs|m0,|4X|βs
5281 |m1,|4.|4.|4.|4,|4X|βs|mm |πsuch that |εX|βs|mm
5285 |πis the |εr|πth element of this sequence. The
5293 set of all real |εy|4α=↓|40.Y|β0Y|β1|4.|4.|4.
5298 |πsuch that |εY|βs|mk |πfor 0|4|¬E|4|εk|4|¬E|4m
5303 |πalso belongs to |εT(a|β1a|β2|4.|4.|4.|4a|βr),
5307 |πand this is a measurable set consisting of
5315 the _nite union of dyadic subintervals |εI|βb|m1|1|β.|1|β.|1
5321 |β.|1|mt. |πSince there are only countably many
5328 such dyadic intervals, we see that |εT(a|β1a|β2|4.|4.|4.|4a|
5334 βr) |πis a countable union of dyadic intervals,
5342 and it is therefore measurable. Furthermore,
5348 this argument can be extended to show that the
5357 measure of |εT(a|β1|4.|4.|4.|4a|βr|βα_↓|β10)
5360 |πequals the measure of |εT(a|β1|4.|4.|4.|4a|βr|βα_↓|β11),
5365 |πsince the latter is a union of dyadic intervals
5374 obtained from the former by requiring that |εY|βs|mk|4α=↓|4X
5381 |βs|mk |πfor |ε0|4|¬E|4k|4|¬W|4m |πand |εY|βs|mm|4|=|↔6α=↓|4
5385 X|βs|mm. |πNow since|'{A9}|εT(a|β1|4.|4.|4.|4a|βr|βα_↓|β10)|
5388 4|↔q|4T(a|β1|4.|4.|4.|4a|βr|βα_↓|β11)|4|↔Y|4T(a|β1|4.|4.|4.|
5388 4a|βr|βα_↓|β1),|;{A9}|πthe measure of |εT(a|β1a|β2|4.|4.|4.|
5392 4a|βr) |πis at most one-half the measure of |εT(a|β1|4.|4.|4
5400 .|4a|βr|βα_↓|β1). |πThe inequality (32) follows
5405 by induction on |εr.|'!|9|7|πNow that (32) has
5413 been established, the remainder of the proof
5420 is essentially to show that the binary representations
5428 of almost all real numbers are equi|-distributed.
5435 The next few paragraphs constitute a rather ling
5443 but not di∃cult proof of this fact, and they
5452 serve to illustrate typical estimation techniques
5458 in mathematical{U0}{H10L12M29}|πW58320#Computer
folio 212 galley 7
5460 Programming!(Knuth/Addison-Wesley)!f.|4212!ch.|43!g.|47d|'
5461 {A6}!|9|7For |εo|4|¬W|4|≤e|4|¬W|41, |πlet |εB(r,|4|≤e)
5465 |πbe |↔e|4|εT(a|β1|4.|4.|4.|4a|βr), |πwhere the
5469 union is taken over all binary numbers |εa|β1|4.|4.|4.|4a|βr
5476 |πfor which the number |ε|≤n(r) |πof zeros among
5485 |εa|β1|4.|4.|4.|4a|βr |πsatis_es|'{A9}|ε|¬G|≤n(r)|4α_↓|4|f1|
5487 d32|)r|¬G|4|¬R|41|4α+↓|4|≤er.|;{A9}|πThe number
5490 of such binary numbers is |εC(|εr,|4|≤e)|4α=↓|4|¬K|4(|fr|d3k
5495 |)) |πsummed over the values of |εk |πwith |ε|¬Gk|4α_↓|4|f1|
5503 d32|)r|¬G|4|¬R|41|4α+↓|4|≤er. |πA suitable estimate
5507 for the tail of the binomial distribution can
5515 be obtained by the following standard trick:
5522 Let |εx |πbe any positive number less than 1,
5531 and let |εs|4α=↓|4(|f1|d32|)|4α+↓|4|≤e)r. |πThen|'
5535 {A9}|ε|↔k|uc|)k|¬Rs|)|1|1|↔a|(r|d5k|)|↔s|4|¬E|4|↔k|uc|)k|¬Rs
5535 |)|1|1|↔a|(r|d5k|)|↔sx|gs|gα_↓|gk|4|¬E|4|↔k|uc|)k|¬R0|)|1|1|
5535 ↔a|(r|d5k|)|↔sx|gs|gα_↓|gk|4α=↓|4x|g5|↔a1|4α+↓|4|(1|d2x|)|↔s
5535 |gr.|;{A9}|πBy elementary calculus, the minimum
5541 value of |εx|gs(1|4α+↓|41/x)|gr |πoccurs when
5546 |εx|4α=↓|4r/s|4α_↓|41|4α=↓|4(1|4α_↓|42|≤e)/(1|4α+↓|42|≤e),
5547 |πand this value of |εx |πyields|'{A9}|ε|↔k|uc|)k|¬R(1/2α+↓|
5553 ≤e)r|)|1|1|↔a|(r|d5k|)|↔s|4|¬E|4|↔a|(2|d2(1|4α+↓|42|≤e)|g1|g
5553 /|g2|gα+↓|g|≤e(1|4α_↓|42|≤e)|g1|g/|g2|gα_↓|g|≤e|)|↔s|gr.|;
5554 {A9}|πNow when |ε|≤e|4|¬W|4|f1|d32|) |πwe have|'
5559 {A9}|ε(|f1|d32|)|4α+↓|4|≤e)|πln(1|4α+↓|4|ε2|≤e)|4α+↓|4(|f1|d
5559 32|)|4α_↓|4|≤e)|πln(1|4α_↓|42|ε|≤e)|4α=↓|4|(1|d21|4αo↓|42|)|
5559 4(2|≤e)|g2|4α+↓|4|(1|d23|4αo↓|44|)|4(2|≤e)|g4|4α+↓|4|(1|d25|
5559 4αo↓|46|)|4(2|≤e)|g6|4α+↓|4αo↓|4αo↓|4αo↓|4|¬Q|42|≤e|g2,|;
5560 {A9}|πhence the denominator in our estimate is
5567 larger than |εe|gα_↓|g2|g|≤e|i2. |πWe have proved
5573 that|'{A9}|ε|↔k|uc|)k|¬R(1/2α+↓|≤e)r|)|1|1|↔a|(r|d5k|)|↔s|4|
5574 ¬W|42|gre|gα_↓|g2|g|≤e|i2r,!!|πfor all!!|εr|4|¬Q|40!!|πand!!
5575 0|4|¬W|4|ε|≤e|4|¬W|4|f1|d32|).|J!(33)|;{A9}|πBut
5577 |εC(r,|4|≤e) |πis twice this left-hand quantity,
5583 hence by (32) and (33)|'{A9}|εB(r,|4|≤e)!!|πhas
5589 measure!!|ε|→|¬E2|gα_↓|grC(r,|4|≤e)|4|¬W|42e|gα_↓|g2|g|≤e|i2
5589 |gr.|;{A9}|π!|9|7The next step is to de_ne|'{A9}|εB|¬S(r,
5597 |≤e)|4α=↓|4B(r, |≤e)|4|↔q|4B(r|4α+↓|41, |≤e)|4|↔q|4B(r|4α+↓|
5599 42, |≤e)|4|↔q|4αo↓|4αo↓|4αo↓|4.|;{A9}|πThe measure
5603 of |εB|¬S(r,|4|≤e) |πis at most |ε|¬K|βk|β|¬R|βr|4ke|gα_↓|g|
5608 ≤e|i2|gk, |πand this is the remainder of a convergent
5617 series so|'{A9}|uwlim|uc|)|.|εr|¬M|¬X|)|4(|πmeasure
5620 of |εB|¬S(r, |≤e){H12}){H10}|4α=↓|40.|J!(34)|;
5623 {A9}!|9|7|πNow if |εx |πis a real number whose
5631 binary expansion |ε0.X|β0X|β1|4.|4.|4. |πleads
5635 to an in_nite sequence |ε|↔bX|βs|mn|↔v|λR |πthat
5641 is not 1-distributed, and if |ε|≤n(r) |πdenotes
5648 the number of zeros in the _rst |εr |πelements
5657 of the latter sequence, then|'{A9}|ε|¬G|≤n(r)/r|4α_↓|4|f1|d3
5662 2|)|↔G|4|¬R|42|≤e,|;{A9}|πfor some |ε|≤e|4|¬Q|40
5666 |πand in_nitely many |εr. |πThis means |εx |πis
5674 in |εB|¬S(r,|4|≤e) |πfor all |εr. |πSo _nally
5681 we _nd that|'{A3}|εN(|λR, |λS)|4α=↓|4|uw|↔e|uc|)t|¬R2|)|4|uw
5685 |↔E|)r|¬R1|)|4B|¬S(r, 1/t),|;{A9}|πand, by (34),
5690 |↔E|β|εr|β|¬R|β1|4B|¬S(r,|41/t) |πhas measure
5693 zero for all |εt. |πHence |εN(|λR,|4|λS) |πhas
5700 measure zero.|'{A12}!|9|7From the existence of
5706 |εbinary |πsequences satisfying De_nition R6,
5711 we can show the existence if [0,|41) sequences
5719 which are random in this sense. For details,
5727 see exercise 36. The consistency of De_nition
5734 R6 is thereby established.|'{A12}|≡E|≡.|9|≡R|≡a|≡n|≡d|≡o|≡m
5739 |≡_|≡n|≡i|≡t|≡e |≡s|≡e|≡q|≡u|≡e|≡n|≡c|≡e|≡s|≡.|9|4An
5741 argument was given above to indicate that it
5749 is impossible to de_ne the concept of randomness
5757 for _nite sequences; any given _nite sequence
5764 is as likely as any other. Still, nearly everyone
5773 would agree that the sequence 011101001 is ``more
5781 random'' than 101010101, and even the latter
5788 sequence is ``more random'' than 000000000. Although
5795 it is true that truly random sequences will exhibit
5804 locally nonrandom behavior, we would expect such
5811 behavior only in a long _nite sequence, not in
5820 a short one.|'!|9|7Several ways for de_ning the
5828 randomness of a _nite sequence have been proposed,
5836 and only a few of the ideas will be sketched
5846 here. Let us consider only the case of |εb|π-ary
5855 sequences.|'!|9|7Given a |εb-|πary sequence |εX|β1,|4X|β2,|4
5860 .|4.|4.|4X|βN, |πwe can say that|'{A9}Pr{H12}({H10}|εS(n){H1
5865 2}){H10}|4|¬V|4p,!!|πif!!|ε|¬G|≤n(N)/N|4α_↓|4p|¬G|4|¬E|41/|¬
5865 H|v4N|),|;{A9}|πwhere |ε|≤n(n) |πis the quantity
5871 appearing in De_nition A at the beginning of
5879 this section. The above sequence can be called
5887 ``|εk-|πdistributed'' if|'{A9}Pr(|εX|βnX|βn|βα+↓|β1|4.|4.|4.
5889 |4X|βn|βα+↓|βk|βα_↓|β1|4α=↓|4x|β1x|β2|4.|4.|4.|4x|βk)|4|¬V|4
5889 1/b|gk|;{A9}|πfor all |εb-|πary numbers |εx|β1x|β2|4.|4.|4.|
5894 4x|βk. (|πCf. De_nition D; unfortunately a sequence
5901 may be |εk-|πdistributed by this new de_nition
5908 when it is not (|εk|4α_↓|41)-|πdistributed.)|'
folio 214 galley 8
5913 |Hu*?*?*?*?{U0}{H10L12M29}|πW58320#Computer Programming!(Knuth/A
5914 ddison-Wesley)!f.|4214!ch.|43!g.|48d|'{A6}!|9|7A
5916 de_nition of randomness may now be given analogous
5924 to De_nition R1, as follows:|'{A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|
5929 ≡n |≡Q|≡1|≡.|9|4|εA b-ary sequence of length
5935 N is ``random'' if it is k-distributed (in the
5944 above sense) for all positive integers k|4|¬E|4|πlog|ε|βb|4N
5950 .|'{A12}!|9|7|πAccording to this de_nition, for
5956 example, there are 170 nonrandom binary sequences
5963 of length 11:|'{A9}|∂00000001111!!10000000111!!11000000011!!
5966 11100000001|;00000001110!!10000000110!!11000000010!!11100000
5967 000|;00000001101!!10000000101!!11000000001!!10100000001|;
5969 00000001011!!10000000011!!01000000011!!01100000001|;
5970 |L00000000111>{A9}plus 01010101010 and all sequences
5976 with nine or more zeros, plus all sequences obtained
5985 from the preceding ones by interchanging ones
5992 and zeros.|'!|9|7Similarly, we can formulate
5998 a de_nition for _nite sequences analogous to
6005 De_nition R6. Let |≡A be a set of algorithms,
6014 each of which is a combination selection and
6022 choice procedure that gives a subsequence |ε|↔bX|βs|mn|↔v|λR
6028 , |πas in the proof of Theorem M.|'{A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡
6036 i|≡o|≡n |≡Q|≡2|≡.|9|4|εThe b-ary sequence X|β1,|4X|β2,|4.|4.
6040 |4.|4,|4X|βN is (n,|4|≤e)-random with respect
6045 to a set of algorithms |π|≡A, |εif for every
6054 subsequence X|βt|m1,|4X|βt|m2,|4.|4.|4,|4X|βt|mm
6056 determined by an algorithm of |π|≡A |εwe have
6064 either m|4|¬W|4n or|'{A9}|↔g|4|(1|d2m|)|4|≤v|βa(X|βt|m1,|4.|
6067 4.|4.|4,|4X|βt|mm)|4α_↓|4|(1|d2b|)|4|↔g|4|¬E|4|≤e!!|πfor!!|ε
6067 0|4|¬E|4a|4|¬W|4b.|;{A9}|πHere |ε|≤n|βa(x|β1,|4.|4.|4.|4,|4x
6069 |βm) |πis the number of |εa|π's in the sequence
6078 |εx|β1,|4.|4.|4.|4,|4x|βm.|'!|9|7|π(In other
6081 words, ev ery su∃ciently long subsequence determined
6088 by an algorithm of |≡A must be approximately
6096 equi|-distributed.) The basic idea in this case
6103 is to let |≡A be a set of ``simple'' algorithms;
6113 the number (and the complexity) of the algorithms
6121 in |≡A can grow as |εN |πgrows.|'!|9|7As an example
6131 of De_nition Q2, let us consider binary sequences,
6139 and let |≡A be just the following four algorithms:|'
6148 {A12}!|9|7a)|9|1Take the whole sequence.|'!|9|7b)|9Take
6153 alternative terms of the sequence, starting with
6160 the _rst.|'!|9|7c)|9|1|1Take the terms of the
6167 sequence following a zero.|'!|9|7d)|9Take the
6173 terms of the sequence following a one.|'{A12}Now
6181 a sequence |εX|β1,|4.|4.|4.|4,|4X|β8 |πis (4,|4|f1|d38|))-ra
6185 ndom if:|'{A12}{I2.11H}by|7(a),|9|1|¬G|f1|d38|)(|εX|β1|4α+↓|
6187 4αo↓|4αo↓|4αo↓|4α+↓|4X|β8)|4α_↓|4|f1|d32|)|¬G|4|¬E|4|f1|d38|
6187 ), |πif there are 3, 4, or 5 ones;|'{A6}by|7(b),|9|¬G|f1|d34
6196 |)(|εX|β1|4α+↓|4X|β3|4α+↓|4X|β5|4α+↓|4X|β7)|4α_↓|4|f1|d32|)|
6196 ¬G|4|¬E|4|f1|d38|), |πi.e., if there are two
6202 ones in odd-numbered positions.|'{A6}by|7(c),|9|1|1there
6207 are three possibilities depending on how many
6214 zeros occupy positions |εX|β1,|4.|4.|4.|4,|4X|β7:
6218 |πif there are 2 or 3 zeros here, there is no
6229 condition to test (since |εn|4α=↓|44); |πif there
6236 are 4 zeros, they must be followed by two zeros
6246 and two ones; and if there are 5 zeros, they
6256 must be followed by two or three zeros.|'{A12}{IC}by|7(d),|9
6264 we get conditions similar to those implied by
6272 (c).|'!|9|7It turns out that only the following
6280 binary sequences of length 8 are (4,|4|f1|d38|))-random
6287 with respect to these rules:|'{A9}00001011!!00101001!!010011
6292 10!!01101000|;00011010!!00101100!!01011011!!01101100|;
6294 00011011!!00110010!!01011110!!01101101|;00100011!!00110011!!
6295 01100010!!01110010|;00100110!!00110110!!01100011!!01110110|;
6297 00100111!!00111001!!01100110!!!!!!|4|4|;{A9}plus
6299 those obtained by interchanging 0 and 1 consistently.|'
6307 !|9|7It is clear that we could make the set of
6317 algorithms so large that no sequencex satisfy
6324 the de_nition, when |εn |πand |ε|≤e |πare reasonably
6332 small. A. N. Kolomogorov has proved that an (|εn,|4|≤e)-|πra
6340 ndom binary sequence |εwill |πalways exist, for
6347 any given |εN, |πif the number of algorithms
6355 in |≡A |πdoes not exceed|'{A9}|ε|f1|d32|)e|g2|gn|g|≤e|i2|g(|
6360 g1|gα_↓|g|≤e|g).|J!(35)|;{A9}|πThis result is
6364 not nearly strong enough to show that sequences
6372 satisfying De_nition Q1 will exist, but the latter
6380 can be constructed e∃ciently using the procedure
6387 of Rees in exercise 3.2.2-21.|'!|9|7Still another
6394 interesting approach to a de_nition of randomness
6401 has been taken by Per Martin-L|=4of [|εInformation
6408 and Control |≡9 (1966), |π602<619]. Given a _nite
6416 |εb-|πary sequence |εX|β1,|4.|4.|4.|4,|4X|βN,
6419 |πlet |ε|λ3(X|β1,|4.|4.|4.|4,|4X|βN) |πbe the
6423 length of the shortest Turing machine program
6430 which generates this sequence. (For a de_nition
6437 of Turing machines, see Chapter 11; alternatively,
6444 we could use certain |πclasses of e=ective algorithms,
6452 such as those de_ned in exercise 1.1<8.) Then
6460 |λ3(|εX|β1,|4.|4.|4.|4,|4X|βN) |πis a measure
6464 of the ``patternlessness'' of the sequence, and
6471 we may equate this idea with randomness. The
6479 sequences of length |εN |πwhich maximize |ε|λ3(X|β1,|4.|4.|4
6485 .|4,|4X|βN) |πmay be called random. (From the
6492 standpoint of practical random-number generation
6497 by computer, this is, of course, the worst de_nition
6506 of ``randomness'' that can be imagined*3)|'!|9|7Essentially
6513 the same de_nition of randomness was independently
6520 given by G. Chaitin at about the same time; see
6530 |εJ|4ACM|4|≡1|≡6 (1969), 145<159. |πIt is interesting
6536 to note that eaen though this de_nition makes
6544 no reference to equi|-distribution properties
6549 as our other de_nitions have, Martin-L|=4of and
6556 Chaitin have proved that random sequences of
6563 this type also have the expected equi|-distribution
6570 properties. In fact, Martin-L|=4of has demonstrated
6576 that such sequences satisfy |εall |πcomputable
6582 statistical tests for randomness, in an appropriate
6589 sense.|'{A12}|≡F|≡.|9|≡S|≡u|≡m|≡m|≡a|≡r|≡y|≡,
6591 |≡h|≡i|≡s|≡t|≡o|≡r|≡y|≡, |≡a|≡n|≡d |≡b|≡i|≡b|≡l|≡i|≡o|≡g|≡r|
6593 ≡a|≡p|≡h|≡y|≡.|9|4We have de_ned several degrees
6598 of randomness that a sequence might possess.|'
6605 !|9|7!|9|7An in_nite sequence which is |¬X-distributed
6611 satis_es a great many useful properties which
6618 are expected of random sequences, and there is
6626 a rich theory concerning |¬X-distributed sequences.
6632 (The exercises which follow develop several important
6639 properties of |¬X-distriguted sequences which
6644 have not been mentioned in the text.) De_nition
6652 R1 is therefore an appropriate basis for theoretical
6660 studies of randomness.|'!|9|7The concept of an
6667 |¬X-distributed |εb-|πary sequence was introduced
6672 in 1909 by Emile Borel. He essentially de_ned
6680 the concept of an (|εm,|4k)-|πdistributed sequence,
6686 and showed that the |εb-|πary representations
6692 of almost all real numbers are (|εm,|4k)-|πdistributed
6699 for all |εm |πand |εk. |πHe called such numbers
6708 |εnormal |πto base |εb. |πAn excellent discussion
6715 of this topic appears in his well-known book,
6723 |εLe|=&cons sur la th|=1eorie des fonctions (|π2nd
6730 ed., 1914), 182<216.|'!|9|7The notion of an |¬X-distributed
6738 sequence of |εreal |πnumbers, also called a |εcompletely
6746 equidistributed sequence, |πwas introduced by
6751 N. M. Korobov in |εDoklady Akad. Nauk |πSSSR
6759 |≡6|≡2 (1948), 21<22. He and several colleagues
6766 developed the theory of such sequences quite
6773 extensively during the 1950s in a series of papers.
6782 The book |εUniform Distribution of Sequences
6788 |πby L. Kuipers and H. Niederreiter (New York:
6796 Wiley, 1974) is an extraordinarily complete source
6803 of information about the rich mathematical literature
6810 concerning |εk-|πdistributed sequences of all
6815 kinds.|'!|9|7We have seen, however, that |¬X-distributed
6822 sequences need not be su∃ciently haphazard to
6829 qualify completely as ``random.'' Three de_nitions,
6835 R4, R5, and R6, were formulated above to provide
6844 the additional conditions; and De_nition R6,
6850 in particular, seems to be an appropriate way
6858 to de_ne the concept of an in_nite random sequence.
6867 It is a precise, quantitative statement that
6874 may well coincide with the intuitive idea of
6882 true randomness.|'|Ha*?*?*?*?{U0}{H10L12M29}|πW58320#Computer
folio 216 galley 9
6885 Programming!(Knuth/Addison-Wesley)!f.|4216!ch.|43!g.|49d|'
6886 {A6}Historically, the development of these de_nitions
6892 was primarily in⊗uenced by R. von Mises' quest
6900 for a good de_nition of ``probability.'' In |εMath.
6908 Zeitschrift |≡5 |π(1919), 52<99, von Mises proposed
6915 a de_nition similar in spirit to De_nition R5,
6923 although stated too strongly (like our De_nition
6930 R3) so that no sequences satisfying the conditions
6938 could possibly exist. Many people noticed this
6945 discrepancy, and A. H. Copeland [|εAmer. J. Math.
6953 |≡5|≡0 (1928), 535<552] |πsuggested weakening
6958 von Mises' de_nition by substituting what he
6965 called ``admissible numbers'' (or Bernoulli sequences).
6971 These are equivalent to |¬X-distributed [0,|41)
6977 sequences in which all entries |εU|βn |πhave
6984 been replaced by 1 if |εU|βn|4|¬W|4p |πor by
6992 0 if |εU|βn|4|¬R|4p, |πfor a given probability
6999 |εp. |πThus Copeland was essentially suggesting
7005 a return to De_nition R1. Then Abraham Wald showed
7014 that it is not necessary to weaken von Mises'
7023 de_nition so drastically, and he proposed substituting
7030 a countable set of subsequence rules. In an important
7039 paper [|εErgebnisse eines math. Kolloquiums |≡8
7045 (|πVienna, 1937), 38<72], Wald essentially proved
7051 Theorem W, although he made the erroneous assertion
7059 that the sequence constructed by Algorithm W
7066 also satis_es the stronger condition that Pr(|εU|βn|4|¬A|4A)
7072 |4α=↓|4|πmeasure of |εA, |πfor all Lebesgue Measurable
7079 |εA|4|↔Y|4[0,|41). |πWe have observed that no
7085 sequence can satisfy this property.|'!|9|7The
7091 concept of ``computability'' was still very much
7098 in its infancy when Wald wrote his paper, and
7107 A. Church [|εBulletin AMS |≡4|≡7 (1940), |π130<135]
7114 showed how the precise notion of ``e=ective algorithm''
7122 could be added to Wald's theory to make his de_nitions
7132 completely rigorous. The extension to De_nition
7138 R6 was due essentially to A. N. Kolmogorov [|εSankhy|=|¬3a
7147 |πseries A, |≡2|≡5 (1963), 369<376], who proposed
7154 De_nition Q2 for _nite sequences in that same
7162 paper.|'!|9|7Another important contribution was
7167 made by Donald W. Loveland [|εZeitschr. f. math.
7175 Logik und Grundlagen d. Math. |≡1|≡2 (1966),
7182 279<294], |πwho discussed De_nitions R4, R5,
7188 R6, and several concepts in between. Loveland
7195 proved that there are R5|4α=↓|4random sequences
7201 which do not satisfy R4, thereby establishing
7208 the need for a stronger de_nition such as R6.
7217 In fact, he de_ned a rather simple permutation
7225 |↔b|εf(n)|↔v |πof the nonnegative integers, and
7231 an Algorithm W|¬S analogous to Algorithm W, such
7239 that |v4Pr|)(|εU|βf|β(|βn|β)|4|¬R|4|f1|d32|))|4α_↓|4|πPr(|εU
7240 |βf|β(|βn|β)|4|¬R|4|f1|d32|))|4|¬R|4|f1|d32|)
7241 |πfor every R5|4α=↓|4random sequence |ε|↔bU|βn|↔v
7246 |πproduced by Algorithm W|¬S when it is given
7254 an in_nite set of subsequence rules |λR|ε|βk.
7261 |πSchnorr's subsequent book |εZuf|=4alligkeit
7265 und Wahrscheinlichkeit [Lecture Notes in Math.
7271 |≡2|≡1|≡8 (|πBerlin: Springer, 1971)] gives a
7277 much more detailed treatment of the entire subject
7285 of randomness than could be provided here and
7293 makes an excellent introduction to the ever-growing
7300 advanced literature on the topic.|'!|9|7The publications
7307 of Church and Kolmogorov considered only binary
7314 sequences for which Pr(|εX|βn|4α=↓|41)|4α=↓|4p
7318 |πfor a given probability |εp. |πThe discussion
7325 which appears in this section is slightly more
7333 general, since a [0,|41) sequence essentially
7339 represents all |εp |πat once.|'!|9|7In another
7346 paper [|εProblemy Pereda|=|≠3ci Inform acci |≡1
7352 (1965), 3<11], |πKolmogorov considered the problem
7358 of de_ning the ``information content'' of a sequence,
7366 and this work led to Chaitin and Martin-L|=4of's
7374 interesting de_nition of _nite random sequences
7380 via ``patternlessness.'' (See |εIEEE Trans. |π|≡I|≡T|≡-|≡1|≡
7385 4 (1968), 662<664.) Another de_nition of randomness,
7392 somewhere ``between'' De_nitions Q1 and Q2, had
7399 been formulated many years earlier by A. S. Besicovitch
7408 [|εMath. Zeitschrift |≡3|≡9 (|π1934), 146<156].|'
7413 !|9|7For further discussion of random sequences,
7419 see K. R. Popper, |εThe Logic of Scienti⊂c Discovery
7428 (|πLondon, 1959), especially the interesting
7433 construction on pp. 162<163, which he _rst published
7441 in 1934.|'{A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A12}{H9L11}|9|1
7444 |≡1|≡.|9|4[|*/|↔O|↔c|\] Can a periodic sequence
7449 be equidistributed?|'{A3}|9|1|≡2|≡.|9|4[|*/|↔O|↔c|\]
7452 Consider the periodic binary sequence 0,|40,|41,|41,|40,|40,
7457 |41,|41,|4.|4.|4.|4. Is it 1-distributed? Is
7462 it 2-distributed? Is it 3-distributed?|'{A3}|9|1|≡3|≡.|9|4[|
7467 ε|*/M|↔P|↔P|\] |πConstruct a periodic ternary
7472 sequence which is 3-distributed.|'{A3}|9|1|≡4|≡.|9|4[|ε|*/HM|
7476 ↔P|↔P|\] |πLet |εU|βn|4α=↓|4(2|g|"l|g|πl|gg|g(|ε|gn|gα+↓|g1|
7478 g)|g|"L/3)|πmod|41. What is Pr(|εU|βn|4|¬W|4|f1|d32|))?|'
7482 {A3}|9|1|≡5|≡.|9|4[|*/HM|↔O|↔M|\] |πProve that
7485 Pr{H11}({H9}|εS(n) |πand T(n){H11}){H9}|4α+↓|4Pr{H11}({H9}|ε
7487 S(n) |πor |εT(n){H11}){H9}|4α=↓|4|πPr{H11}({H9}|εS(n){H11}){
7489 H9}|4α+↓|4|πPr{H11}({H9}|εT(n){H11}){H9}, |πfor
7491 any two statements |εS(n), T(n), |πprovided at
7498 least three of the limits exist. [For example,
7506 if a sequence is 2-distributed, we would _nd
7514 that|'{A9}{H9}Pr(|εu|β1|4|¬E|4U|βn|4|¬W|4v|β1!!|πor!!|εu|β2|
7515 4|∂|¬E|4U|βn|βα+↓|β1|4|¬W|4v|β2)|hα_↓(v|β1|4α_↓|4u|β1))v|β2|
7515 4α_↓|4u|β2).]|n|;{A4}|Lα=↓|4v|β1|4α_↓|4u|β1|4α+↓|4v|β2|4α_↓|
7516 4u|β2|4α_↓|4(v|β1|4α_↓|4u|β1)(v|β2|4α_↓|4u|β2).]>
7517 {A9}|9|1|≡6|≡.|9|4[|*/HM|↔P|↔L|\] |πLet |εS|β1(n),
7520 S|β2(n),|4.|4.|4. |πbe an in_nite sequence of
7526 statements about mutually disjoint events, i.e.,
7532 |εS|βi(n) |πand |εS|βj(n) |πcannot simultaneously
7537 be true if |εi|4|=|↔6α=↓|4j. |πAssume that Pr{H11}({H9}S|βj(
7543 n){H11}){H9} exists for each |εj|4|¬R|41. |πShow
7549 that Pr{H11}({H9}|εS|βj(n) |πis true for some
7555 |εj|4|¬R|41{H11}){H9}|4|¬R|4|¬K|βj|β|¬R|β1|4|πPr{H11}({H9}|ε
7555 S|βj(n){H11}){H9}, |πand give an example to show
7562 that equality need not hold.|'{A3}|9|1|≡7|≡.|9|4[|ε|*/HM|↔P|↔
7567 p|\] |πAs in the previous exercise, let |εS|βi|βj(n),
7575 i|4|¬R|41, j|4|¬R|41, |πbe in_nitely many mutually
7581 disjoint events, such that Pr{H11}({H9}|εS|βi|βj(n){H11}){H9
7585 } |πexists. Assume that for all |εn|4|¬Q|40,
7592 S|βi|βj(n) |πis true for exactly one pair of
7600 integers |εi,|4j. |πIf |¬K|ε|βi|β,|βj|β|¬R|β1|4|πPr{H11}({H9
7603 }|εS|βi|βj(n){H11}){H9}|4α=↓|41, |πcan it be
7607 concluded that, for all |εi|4|¬R|41, |πPr{H11}({H9}|εS|βi|βj
7612 (n) |πis true for some |εj|4|¬R|41{H11}){H9}
7618 |πexists and equals |¬K|ε|βj|β|¬R|β1|4|πPr{H11}({H9}|εS|βi|β
7621 j(n){H11}){H9}?|'{A3}|9|1|≡8|≡.|9|4[M|*/|↔O|↔C|\]
7623 |πProve (13).|'{A3}|9|1|≡9|≡.|9|4[|εHM|*/|↔P|↔c|\]
7626 |πProve Lemma E. [|εHint|*/: |\|πConsider |¬K|ε|β1|β|¬E|βj|β|
7631 ¬E|βm|4(y|βj|βn|4α_↓|4|≤a)|g2.]|'{A3}|≡1|≡0|≡.|9|4[|*/HM|↔P|↔
7632 P|\] |πWhere was the fact that |εq |πis a multiple
7642 of |εm |πused in the proof of Theorem C?|'{A3}|≡1|≡1|≡.|9|4|
7651 ε[M|*/|↔O|↔c|\] |πUse Theorem C to prove that
7658 if |↔b|εU|βn|↔v |πis |¬X-distributed, so is the
7665 subsequence |ε|↔bU|β2|βn|↔v.|'{A3}|≡1|≡2|≡.|9|4[|*/HM|↔P|↔c|\
7667 ] |πShow that a |εk-|πdistributed sequence passes
7674 the ``maximum of |εk'' |πtest, in the following
7682 sense: Pr{H11}({H9}|εu|4|¬E|4|πmax(|εU|βn,|4U|βn|βα+↓|β1,|4.
7683 |4.|4.|4,|4U|βn|βα+↓|βk|βα_↓|β1)|4|¬W|4v{H11}){H9}|4α=↓|4v|g
7683 k|4α_↓|4u|gk.|'{A3}|≡1|≡3|≡.|9|4[|*/HM|↔P|↔p|\]
7685 |πShow that an |¬X-distributed [0,|41) sequence
7691 passes the ``gap test'' in the following sense:
7699 If If 0|4|¬E|4|ε|≤a|4|¬W|4|≤b|4|¬E|41, |πand
7703 |εp|4α=↓|4|≤b|4α_↓|4|≤a, |πlet |εf(0)|4α=↓|40,
7706 |πand for |εn|4|¬R|41, |πlet |εf(n) |πbe the
7713 smallest integer |εm|4|¬Q|4f(n|4α_↓|41) |πsuch
7717 that |ε|≤a|4|¬E|4U|βm|4|¬W|4|≤b; |πthen Pr{H11}({H9}|εf(n)|4
7720 α_↓|4f(n|4α_↓|41)|4α=↓|4k{H11}){H9}|4α=↓|4p(1|4α_↓|4p)|gk|gα
7720 _↓|g1.|'{A3}|≡1|≡4|≡.|9|4[|*/HM|↔P|↔C|\] |πShow
7723 that an |¬X-distributed sequence passes the ``run
7730 test'' in the following sense: If |εf(0)|4α=↓|41
7737 |πand if for |εn|4|¬R|41 f(n) |πis the smallest
7745 integer |εm|4|¬Q|4f(n|4α_↓|41) |πsuch that |εU|βm|βα_↓|β1|4|
7749 ¬Q|4U|βm, |πthen|'{A9}Pr{H11}({H9}|εf(n)|4α_↓|4f(n|4α_↓|41)|
7751 4α=↓|4{H11}){H9}|4α=↓|42k/(k|4α+↓|41)*3|4α_↓|42(k|4α+↓|41)/(k
7751 |4α+↓|42)*3.|;{A9}|≡1|≡5|≡.|9|4[|*/HM|↔L|↔c|\]
7753 |πShow that an |¬X-distributed sequence passes
7759 the ``coupon-collector's test'' when there are
7765 only two kinds of coupons, in the following sense`
7774 Let |εX|β1,|4X|β2,|4.|4.|4. |πbe an |¬X-distributed
7779 binary sequence. Let |εf(0)|4α=↓|40, |πand for
7785 |εn|4|¬R|41 |πlet |εf(n) |πbe the smallest integer
7792 |εm|4|¬Q|4f(n|4α_↓|41) |πsuch that |¬T|εX|βf|β(|βn|βα_↓|β1|β
7795 )|βα+↓|β1,|4.|4.|4.|4,|4X|βm|¬Y |πis the set
7799 |¬T0,|41|¬Y. Prove that Pr{H11}({H9}|εf(n)|4α_↓|4f(n|4α_↓|41
7802 )|4α=↓|4k{H11}){H9}|4α=↓|42|g1|gα_↓|gk, k|4|¬R|42.
7804 |π(Cf. exercise 7.)|'|≡1|≡6|≡.|9|4[|ε|*/HM|↔L|↔l|\]
7808 |πDoes the coupon-collector's test hold for |¬X-distributed
7815 sequences when there are more than two kinds
7823 of coupons? (Cf. the previous exercise.)|'{A3}|≡1|≡7|≡.|9|4|
7829 ε[|*/HM|↔C|↔c|\] |πGiven that |εr |πis a rational
7836 number, Franklin has proved that the sequence
7843 with |εU|βn|4α=↓|4(r|gn|4|πmod|41) is not 2-distributed.
7848 But is there any rational number |εr |πfor which
7857 this sequence is equidistributed? In particular,
7863 is the sequence equidistributed when |εr|4α=↓|4|f3|d32|)?
7869 (|πCf. the article by K. Mahler, |εMathematika
7876 |≡4 (|π1957), 122<124.)|'{A3}|≡1|≡8|≡.|9|4[|ε|*/HM|↔P|↔P|\]
7880 |πProve that if |εU|β0,|4U|β1,|4.|4.|4. |πis
7885 |εk-|πdistributed, so is the sequence |εV|β0,|4V|β1,|4.|4.|4
7890 .|4, |πwhere |εV|βn|4α=↓|4|"lnU|βn|"L/n.|'{A3}|≡1|≡9|≡.|9|4[
7893 |ε|*/HM|↔L|↔C|\] |πConsider De_nition R4 with
7898 ``|¬X-distributed'' replaced by ``1-distributed''.
7902 Is there a sequence which satis_es this weaker
7910 de_nition, but which is not |¬X-distributed?
7916 (Is the weaker de_nition really weaker?)|'{A3}|≡2|≡0|≡.|9|4[
7922 |ε|*/HM|↔M|↔o|\] |πDoes the sequence with |εU|βn|4{U0}{H10L12
folio 220 galley 10
7927 M29}|πW58320#Computer Programming!(Knuth/Addison-Wesley)!f.|
7928 4220!ch.|43!g.|410d|'{A6}|≡2|≡1|≡.|9|4|ε[|*/HM|↔P|↔c|\]
7930 |πLet |εS |πbe a set and let |λM be a collection
7941 of subsets of |εS. |πSuppose that |εp |πis a
7950 real-valued function of the sets in |λM, for
7958 which |εp(M) |πdenotes the probability that a
7965 ``randomly'' chosen element of |εS |πlies in
7972 |εM. |πGeneralize De_nitions B and D to obtain
7980 a good de_nition of the concept of a |εk-|πdistributed
7989 sequence |ε|↔bZ|βn|↔v |πof elements of |εS |πwith
7996 respect to the probability distribution |εp.|'
8002 {A3}|≡2|≡2|≡.|9|4[|*/HM|↔L|↔c|\] (|πHermann Weyl.)
8005 Show that the [0,|41) sequence |ε|↔bU|βn|↔v |πis
8012 |εk-|πdistributed if and only if|'{A4}|uwlim|uc|)|.|εN|¬M|¬X
8017 |)|4|(1|d2N|)|4|↔k|uc|)0|¬En|¬WN|)|4|πexp{H11}({H9}|ε2|≤pi(c
8017 |β1U|βn|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|βkU|βn|βα+↓|βk|βα_↓|β1){
8017 H11}){H9}|4α=↓|40|;{A6}{A3}|πfor every set of
8022 integers |εc|β1,|4c|β2,|4.|4.|4.|4,|4c|βk |πnot
8025 all zero.|'{A3}|≡2|≡3|≡.|9|4[|ε|*/M|↔L|↔M|\] |πShow
8029 that a |εb-|πary sequence |ε|↔bX|βn|↔v |πis |εk-|πdistribute
8035 d if and only if all of the sequences |ε|↔bc|β1X|βn|4α+↓|4c|
8044 β2X|βn|βα+↓|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|βkX|βn|βα+↓|βk|βα
8044 _↓|β1|↔v |πare |εequidistributed, |πwhenever
8048 |εc|β1,|4c|β2,|4.|4.|4.|4,|4c|βk |πare integers
8051 with gcd (|εc|β1,|4.|4.|4.|4,|4c|βk)|4α=↓|41.|'
8054 {A3}{H9}|≡2|≡4|≡.|9|4[|*/M|↔L|↔c|\] |πShow that
8057 a [0,|41) sequence |ε|↔bU|βn|↔v |πis |εk-|πdistributed
8063 if and only if all of the sequences |ε|↔bc|β1U|βn|4α+↓|4c|β2
8071 U|βn|βα+↓|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|βkU|βn|βα+↓|βk|βα_↓
8071 |β1|↔v |πare |εequidistributed, |πwhenever |εc|β1,|4c|β2,|4.
8075 |4.|4.|4,|4c|βk |πare integers not all zero.|'
8081 {A3}|≡2|≡5|≡.|9|4[|ε|*/HM|↔P|↔c|\] |πA sequence
8084 is called a ``white sequence'' if all serial
8092 correlations are zero, i.e., if the equation
8099 in Corollary S is true for |εall k|4|¬R|41. (|πBy
8108 Corollary S, an |¬X-distributed sequence is white.)
8115 Show that if a [0,|41) sequence is equidistributed,
8123 it is white if and only if|'{A9}|uwlim|uc|)|.|εn|¬M|¬X|)|4|(
8130 1|d2n|)|4|↔k|uc|)0|¬Ej|¬Wn|)|4(U|βj|4α_↓|4|f1|d32|))(U|βj|βα
8130 +↓|βk|4α_↓|4|f1|d32|))|4α=↓|40,!!|πall!!|εk|4|¬R|41.|;
8131 {A9}|≡2|≡6|≡.|9|4[|*/HM|↔L|↔M|\] (|πJ. Franklin.)
8134 A white sequence, as de_ned in the previous exercise,
8143 can de_nitely fail to be random. Let |εU|β0,|4U|β1,|4.|4.|4.
8150 |πbe an |¬X-distributed sequence; de_ne the
8157 sequence |εV|β0,|4V|β1,|4.|4.|4. |πas follows:|'
8161 {A9}|ε(V|β2|βn|βα_↓|β1,|4V|β2|βn)|4α=↓|4(U|β2|βn|βα_↓|β1,|4U
8161 |β2|βn)!!|πif!!(|εU|β2|βn|βα_↓|β1,|4U|β2|βn)|4|¬A|4G,|;
8162 {A4}(V|β2|βn|βα_↓|β1,|4V|β2|βn)|4α=↓|4(U|β2|βn,|4U|β2|βn|βα_
8162 ↓|β1)!!|πif!!|ε(U|β2|βn|βα_↓|β1,|4U|β2|βn)|4|=|↔6|¬A|4G,|;
8163 {A9}|πwhere |εG |πis the set |¬T(|εx,|4y)|4|¬G|4x|4α_↓|4|f1|
8168 d32|)|4|¬E|4y|4|¬E|4x |πor |εx|4α+↓|4|f1|d32|)|4|¬E|4y|¬Y.
8171 |πShow that (a) |εV|β0,|4V|β1,|4.|4.|4. |πis
8176 equidistributed and white; (b) Pr(|εV|βn|4|¬Q|4V|βn|βα+↓|β1)
8180 |4α=↓|4|f5|d38|). (|πThis points out the weakness
8186 of the serial correlation test.)|'{A3}|ε|≡2|≡7|≡.|9|4[|*/HM|↔
8191 M|↔m|\] |πWhat is the highest possible value
8198 for Pr(|εV|βn|4|¬Q|4V|βn|βα+↓|β1- |πin an equidistributed,
8203 white sequence? (D. Coppersmith [to appear] has
8210 constructed such a sequence achieving the value
8217 |f7|d38|).)|'{A3}|ε|≡2|≡8|≡.|9|4[HM|*/|↔P|↔O|\]
8219 |πUse the sequence (11) to construct a [0,|41)
8227 sequence which is 3-distributed, for which Pr(|εU|β2|βn|4|¬R
8233 |4|f1|d32|))|4α=↓|4|f3|d34|).|'{A3}|≡2|≡9|≡.|9|4[HM|*/|↔L|↔M|
8234 \] |πLet |εX|β0,|4X|β1,|4.|4.|4. |πbe a (|ε2k)-|πdistributed
8239 binary sequence. Show that|'{A9}|v4Pr|)(|εX|β2|βn|4α=↓|40)|
8244 4|¬E|4|f1|d32|)|4α+↓|4|↔a|(2k|4α_↓|41|d5k|)|↔s|↔h2|g2|gk.|;
8245 {A9}|≡3|≡0|≡.|9|4|ε[|*/M|↔L|↔m|\] |πConstruct
8247 a binary sequence which is (|ε2k)-|πdistributed,
8253 and for which|'{A9}Pr(|εX|β2|βn|4α=↓|40)|4α=↓|4|f1|d32|)|4α+
8256 ↓|4|↔a|(2k|4α_↓|41|d5k|)|↔s|↔h2|g2|gk.|;{A9}(|πTherefore
8258 the inequality in the previous exercise is the
8266 best possible.)|'{A3}|ε|≡3|≡2|≡.|9|4[|*/M|↔P|↔M|\]
8269 |πGiven that |ε|↔bX|βn|↔v |πis a ``random'' |εb-|πary
8276 sequence according to De_nition R5, and if |ε|λR
8284 |πis a computable subsequence rule which speci_es
8291 an in_nite subsequence |ε|↔bX|βn|↔v|λR, |πshow
8296 that the latter subsequence is not only 1-distributed,
8304 it is ``random'' by De_nition R5.|'{A3}|ε|≡3|≡3|≡.|9|4[|*/HM|
8310 ↔P|↔M|\] |πLet |ε|↔bU|βs|mn|↔v |πand |ε|↔bU|βs|mn|↔v
8315 |πbe in_nite disjoint subsequences of a sequence
8322 |ε|↔bU|βn|↔v. |π(Thus, |εr|β0|4|¬W|4r|β1|4|¬W|4r|β2|4|¬W|4αo
8324 ↓|4αo↓|4αo↓ |πand |εs|β0|4|¬W|4s|β1|4|¬W|4s|β2|4|¬W|4αo↓|4αo
8326 ↓|4αo↓ |πare increasing sequences of integers
8332 and |εr|βm|4|=|↔6α=↓|4s|βn |πfor any |εm,|4n.)
8337 |πLet |ε|↔bU|βt|mn|↔v |πbe the combined subsequence,
8343 so that |εt|β0|4|¬W|4t|β1|4|¬W|4t|β2|4|¬W|4αo↓|4αo↓|4αo↓
8346 |πand the set |¬T|εt|βn|¬Y|4α=↓|4|¬Tr|βn|¬Y|4|↔q|4|¬Ts|βn|¬Y
8349 . |πShow that if Pr(|εU|βr|mn|4|¬A|4A)|4α=↓|4|πPr(|εU|βs|mn|
8353 4|¬A|4A)|4α=↓|4p, |πthen Pr(|εU|βt|mn|4|¬A|4A)|4α=↓|4p.|'
8356 {A3}|≡3|≡4|≡.|9|4[|*/M|↔P|↔C|\] |πDe_ne subsequence
8359 rules |λR|β1,|4|λR|β2,|4|λR|β3,|4.|4.|4. such
8362 that Algorithm W can be used with these rules
8371 to give an e=ective algorithm to construct a
8379 [0,|41) sequence satisfying De_nition R1.|'{A3}|≡3|≡5|≡.|9|4
8384 |ε[|*/HM|↔L|↔C|\] |π(D. W. Loveland.) Show that
8390 if a binary sequence |ε|↔bX|βn|↔v |πis R5|4α=↓|4random,
8397 and if |ε|↔bs|βn|↔v |πis any computable sequence
8404 as in De_nition R4, we must have |v4Pr|)(|εX|βs|mn|4α=↓|41)|
8411 4|¬R|4|f1|d32|) |πand Pr(|εX|βs|mn|4α=↓|41)|4|¬E|4|f1|d32|).
8413 |'{A3}|≡3|≡6|≡.|9|4[|*/HM|↔L|↔c|\] |πLet |ε|↔bX|βn|↔v
8417 |πbe a binary sequence which is ``random'' according
8425 to De_nition R6. Show that the [0,|41) sequence
8433 |ε|↔bU|βn|↔v |πde_ned in binary notation by the
8440 scheme|'{A9}|ε|∂U|β0|4α=↓|40.X|β0|hX|β7X|β9X|β9|n|;
8442 {A4}|LU|β1|4α=↓|40.X|β1X|β2>{A4}|LU|β2|4α=↓|40.X|β3X|β4X|β5>
8444 {A4}|LU|β3|4α=↓|40.X|β6X|β7X|β8X|β9>{A2}|Lαo↓|4αo↓|4αo↓>
8446 {A9}|πis random in the sense of De_nition R6.|'
8454 {A3}|ε|≡3|≡7|≡.|9|4[|*/M|↔M|↔c|\] (|πD. Coppersmith.)
8457 De_ne a sequence which satis_es De_nition R4
8464 but not De_nition R5. [|εHint|*/: |\|πConsider
8470 changing |εU|β0, U|β1, U|β4, U|β9,|4.|4.|4. |πin
8476 a truly random sequence.]|'|H*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
8480